[KMP]hdoj 3746:Cyclic Nacklace


大体の意味:
    文字列を指定します.最低何文字を追加するかを求めて、この文字列を繰り返し列にします.
 
大体の考え:    KMPの最小カバー部分列の小さい変形、最小カバー部分列の長さはlen-(next[len-1]~~具体的には参照してください.  http://blog.csdn.net/fjsd155/article/details/6866991  また、poj 2185もこのような問題です.
 
 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax= 100005;
const int mMax=1000005;
char pat[nMax];
int lenp,next[nMax];

void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){     //pat[j]        i       next       
        while(j>-1&&pat[j+1]!=pat[i])j=next[j];
        if(pat[j+1]==pat[i])j++;
        next[i]=j;
    }
}

int main(){
    int t,a,b;
    scanf("%d",&t);
    while(t--){
        scanf("%s",pat);
        lenp=strlen(pat);
        get_next();
        a=next[lenp-1]+1;
        a=lenp-a;    //        
        b=lenp%a;
        if(b){
            printf("%d
",a-b); } else{ if(a==lenp){ printf("%d
",lenp); } else{ printf("0
"); } } } return 0; }