Cyclic Nacklace HDU

参考文章：https://blog.csdn.net/u013686535/article/details/52197912

//next[i]可以理解为T(0..i)的前缀与后缀相等
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
const int maxlen = 1e5 + 9;
int t;
char S[maxlen];
int main() {
    scanf("%d", &t);
    while(t--) 
	{
        scanf("%s", S + 1);
        int n = strlen(S + 1);
        int ne[maxlen];
        memset(ne,0,sizeof ne);
        for(int i=2,j=0;i<=n;i++)
		{
            while(j&&S[i]!=S[j+1])
                j=ne[j];
            if(S[i]==S[j+1])
				j++;
            ne[i]=j;
        }
        //循环的长度 
        int p=n-ne[n]; 
        if(ne[n]!=0&&n%p==0)
			cout<<0<<endl;
        else 
			cout<<p-n%p<<endl;
    }
    return 0;
}