【HDU 3746】Simpsons’ Hidden Talents（KMP求循环节）

#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);
    }
}