题目描述
原题来自：POI 2012
给出一个由小写英文字母组成的字符串
S
S，再给出
q
q 个询问，要求回答
S
S 某个子串的最短循环节。
如果字符串
B
B 是字符串
A
A 的循环节，那么
A
A 可以由
B
B 重复若干次得到。
输入
第一行一个正整数
n
n，表示
S
S 的长度。
第二行
n
n 个小写英文字母，表示字符串
S
S 。
第三行一个正整数
q
q ，表示询问个数。
下面
q
q 行每行两个正整数
a,b
a,b ，表示询问字符串
S[a..b]
S[a..b] 的最短循环节长度。
输出
依次输出
q
q 行正整数，第
i
i 行的正整数对应第
i
i 个询问的答案。
样例输入
8
aaabcabc
3
1 3
3 8
4 8
样例输出
1
3
5
提示
数据范围与提示
1 \le a \le b \le n \le {5\times 10^5} ,
1≤a≤b≤n≤5×105,
q \le {2\times 10 ^ 6}
q≤2×106。
来源/分类
ybttg hash 数论