A61791 | $信息学奥赛练习题：A Horrible Poem【$

来源2023年

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

信息学奥赛练习题：A Horrible Poem 【题目描述】 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。 如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。 【输入】 第一行一个正整数 n，表示 S 的长度。 第二行 n 个小写英文字母，表示字符串 S 。 第三行一个正整数 q ，表示询问个数。 下面 q 行每行两个正整数 a,b，表示询问字符串 S[a..b] 的最短循环节长度。 【输出】 依次输出 q 行正整数，第 i 行的正整数对应第 i 个询问的答案。 【输入样例】 8 aaabcabc 3 1 3 3 8 4 8 【输出样例】 135 【提示】 1\leqa\leqb\leqn\leq5\times10 5, q\leq2\times10 6 。

C++ 编辑器

输入

输出