Description


给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到。

Input

 

第一行一个正整数n (n<=500,000),表示S的长度。
第二行n个小写英文字母,表示字符串S。
第三行一个正整数q (q<=2,000,000),表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n),表示询问字符串S[a..b]的最短循环节长度。

Output

依次输出q行正整数,第i行的正整数对应第i个询问的答案。

Sample Input

8
aaabcabc
3
1 3
3 8
4 8

Sample Output

1
3
5

HINT

Source

鸣谢 jiangzoi&oimaster

n是[l,r]这一段的循环节的充要条件是[l,r-n]和[l+n,r]相同 且n是长度的约数

如果枚举长度区间的所有约数是sqrt(n)的复杂度  考虑如何优化

有一条性质:若len是循环节 则k*len|n均是循环节

那么我们可以首先将每次询问 log时间内分解质因数 然后检查除以这个质因数之后这个是否是循环节 然后因为每次除的都是质因数可以保证整体还是个循环节

那么这个log时间分解质因数就线性筛即可

 

 

分类: hash筛法

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论