[HDU 3746]Cyclic Nacklace[kmp求周期]

#include   
#include   
const int MAXN = 100005;  
int next[MAXN];  
char s[MAXN];  
//125MS   688K  
void prekmp()  
{  
    next[0] = -1;  
    int j = -1;  
    for(int i=1;s[i];i++)  
    {  
        while(j!=-1 && s[j+1]!=s[i])    j = next[j];  
        if(s[j+1]==s[i])    j++;  
        next[i] = j;  
    }  
}  
  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%s",s);  
        prekmp();  
        int n,len,r,q,add;  
        n = strlen(s);  
        len = n - 1 - next[n-1];  
        r = n % len;  
        q = n / len;  
        if(q==1)  
        {  
            add = 2*len - n;  
        }  
        else  
        {  
            add = (len - r)%len;  
        }  
        printf("%d\n",add);  
    }  
  
}