问题 2313 --A Horrible Poem

2313: A Horrible Poem★★★★

时间限制: 2 Sec  内存限制: 128 MB
提交: 60  解决: 25
[提交][状态][命题人:]

题目描述

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

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

输入

第一行一个正整数 nn，表示 SS 的长度。
第二行 nn 个小写英文字母，表示字符串 SS 。
第三行一个正整数 qq ，表示询问个数。
下面 qq 行每行两个正整数 a,ba,b ，表示询问字符串 S[a..b]S[a..b] 的最短循环节长度。

输出

依次输出 qq 行正整数，第 ii 行的正整数对应第 ii 个询问的答案。
样例输入
Copy
8
aaabcabc
3
1 3
3 8
4 8
样例输出
Copy
1
3
5

提示

1≤a≤b≤n≤5×105, q \le {2\times 10 ^ 6}q≤2×106。

来源

POJ 2012 

[提交][状态]