思路
利用到kmp的next数组的一个性质。
- 最小循环节长度length = plen - next[plen]；
- 如果plen%length == 0（plen!=length） ，那么完全循环。
- 否则需要增加plen - plen%length完成循环。（注意plen==length则需要增加plen）
#include<iostream>
using namespace std;
const int MAXN=10000002;
string P;
string T;
int NEXT[MAXN];
int plen,tlen;
void getNext(){
NEXT[0] = -1;
int k = -1 ;
int j = 0 ;
while(j<plen){
if(k==-1||P[k]==P[j]){
NEXT[++j] = ++k;
}else{
k = NEXT[k];
}
}
}
int main(){
ios::sync_with_stdio(false);
int TT;
cin>>TT;
while(TT--){
cin>>P;
plen = P.length();
getNext();
int length = plen - NEXT[plen];
// for(int i = 0 ;i<plen;i++){
// cout<<NEXT[i]<<" ";
// }
// cout<<"\n";
if(length!=plen&&plen%length==0) {
cout<<0<<"\n";
}
else{
cout<<length - plen%length<<"\n";
}
}
return 0;
}
