Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

12/7
15:47
字符串hash

[bzoj 2795] [Poi2012]A Horrible Poem

♦♦♦♦♦♦   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   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

1、循环节一定是长度的约数

2、如果n是一个循环节,那么k*n也必定是一个循环节

3、n是[l,r]这一段的循环节  的充要条件是  [l,r-n]和[l+n,r]相同

枚举所有的质因子,不断除以原长并保证其仍是循环节,直到不能再小为止。

 

[bzoj 2795] [Poi2012]A Horrible Poem