给出一个由小写英文字母组成的字符串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
Sol:设Len为所求的区间长度，然后对Len这个数字做质因子分解
例如Len=20时，20=2*2*5
首先取出长度为20/2=10的字符串的前缀及后缀，看其是否相等，如果相等则Len=10
然后取出长度为10/2=5的字符串的前缀及后缀，看是否相等，如果不等，则Len不变
然后取出Len=10/5=2的字符串的前缀及后缀，看是否相等。
这个思路其实是求字符串的循环节，可参考Period那个题(Kmp算法)
#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define mod 19260817
using namespace std;
inline void read(ll &x)
{
ll datta=0;char chchc=getchar();bool okoko=0;
while(chchc<‘0‘||chchc>‘9‘){if(chchc==‘-‘)okoko=1;chchc=getchar();}
while(chchc>=‘0‘&&chchc<=‘9‘){datta=datta*10+chchc-‘0‘;chchc=getchar();}
x=okoko?-datta:datta;
}
ll p[N],n,m,q[N],l,r,hx[N],base=29;
ll prime[N],pnum,len,son[N],nn;
char c[N];
bool h[N];
void pre()
{
for(int i=2;i<=n;i++)
{
if(!h[i])
{
prime[++pnum]=i;
p[i]=i;
}
for(int j=1;j<=pnum&&i*prime[j]<=n;j++)
{
h[i*prime[j]]=true;
p[i*prime[j]]=prime[j];
if(!i%prime[j])break;
}
}
q[0]=1;
for(int i=1;i<=n;i++)
q[i]=(q[i-1]*base)%mod;
for(int i=1;i<=n;i++)
{
hx[i]=hx[i-1]*base+c[i]-‘a‘+1;
hx[i]=hx[i]%mod;
}
}
ll fk(ll a,ll b)
{
ll num=hx[b]-(hx[a-1]*q[b-a+1])%mod;
num=(num+mod)%mod;
return num;
}
bool cheak(ll a,ll b,ll l)
//取字符串中长度为L的前缀与后缀
{
if(fk(a,b-l)==fk(a+l,b))
return true;
else
return false;
}
int main()
{
read(n);
scanf("%s",c+1);
pre();
read(m);
for(int i=1;i<=m;i++){
read(l),read(r);
len=r-l+1,nn=0;
while(len!=1)
{
son[++nn]=p[len];
len=len/p[len];
}
len=r-l+1;
for(int j=1;j<=nn;j++)
{
ll now=len/son[j];
if(cheak(l,r,now))
//如果找出循环节,则Len变成Now
len=now;
}
printf("%lld\n",len);
}
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/12297466.html