[KMP-求循环节]HDU 3746 Cyclic Nacklace

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3746

题目大意：给定一个字符串，求出最少在末尾添加几个字符使得字符串成为循环串。

解题思路：先求出最小循环节，如果最小循环节长度等于字符串长度，则添加的字符数为字符串的长度，否则用字符串的长度模循环节的长度，如果为0，说明已经是循环串，如果非0，说明还要添加字符串长度减去该值个字符.

代码：

#include<iostream>
using namespace std;
const int MAXN = 111111;
int T,next[MAXN];
char s[MAXN],t[MAXN];
void makenext(char *s){
    int N = strlen(s);
    int i = 0,j = -1;
    next[0] = -1;
    while(i<=N){
        if(s[i]==s[j]||j==-1)next[++i]=++j;
        else j = next[j];
    }
}

int solve(){
    int N = strlen(s);
    int L = N-next[N];
    if(N==L)return N;
    if(N%L)return L-N%L;
    else return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        makenext(s);
        printf("%d\n",solve());
    }
    return 0;
}