bzoj#P2890. 序列的故事

序列的故事

题目描述

给出一个由小写英文字母组成的字符串 SS,再给出 qq 个询问,要求回答 SS 某个子串的最短循环节。

循环节的定义:如果字符串 BB 是字符串 AA 的循环节,那么 AA 可以由 BB 重复若干次得到。

输入格式

第一行一个整数 nn 表示 SS 的长度。

第二行 nn 个小写字母表示字符串 SS

第三行一个整数 qq 表示询问个数。

接下来 qq 行每行两个整数 l,rl,r,表示询问字符串 S[lr]S[l\dots r] 的最短循环节。

输出格式

qq 行,每行一个整数表示答案。

8
aaabcabc
3
1 3
3 8
4 8
1
3
5

数据规模与约定

对于 30%30\% 的数据,1q1041\leq q\leq 10^4

对于 42%42\% 的数据,1n1041\leq n\leq 10^4

对于 100%100\% 的数据,1n5×1051\leq n\leq 5\times 10^51q2×1061\leq q\leq 2\times 10^6