[KMP]hdoj 3746：Cyclic Nacklace

大致题意：

    给出一个字符串，求最少再增加多少个字符才能使得这个字符串成为一个重复串。

 

大致思路：
    KMP最小覆盖子串的小小变形，最小覆盖子串的长度为len-(next[len-1])~~具体请参见 http://blog.csdn.net/fjsd155/article/details/6866991  另外poj2185也是这类题

 

 

#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\n",a-b);
        }
        else{
            if(a==lenp){
                printf("%d\n",lenp);
            }
            else{
                printf("0\n");
            }
        }
    }
    return 0;
}