求next数组,(一般有两种,求循环节用的见代码)求出循环节的长度。
#include <cstdio>
#define N 100005
int n,next[N];
char s[N];
int main(){
scanf("%d",&n);
while(n--){
scanf("%s",s);
int i=0,k=-1;
next[0]=k;
while(s[i]){
if(k==-1||s[i]==s[k])
{
i++;
k++;
next[i]=k;
}else
k=next[k];
}
int b=i-next[i],ans=0;
if(b==i||i%b)ans=b-i%b;//本身是循环节或者不能完全循环。
printf("%d\n",ans);
}
}