题目

思路

利用到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;
}