题目来源：http://poj.org/problem?id=2406

题目描述：

思路：

利用KMP算法，求字符串的next数组，若len可以被len - next[len]整除，则最大循环次数为len/(len - next[len])，否则为1

ps:题目没说碰到’.'结束，我还以为不用

参考代码:

#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+100;
int nxt[N];
char s[N];
void get_next(int len) {
    int j = 0, k = -1;
    nxt[0] = -1;
    while (j < len)
        if (k == -1 || s[j] == s[k])
            nxt[++j] = ++k;
        else
            k = nxt[k];
}
int main() {
    int i;
    while (scanf("%s", s)&&s[0]!='.') {
        i =strlen(s);
        get_next(i);
            int j = i - nxt[i];
            if (i % j == 0 && i / j > 1)
                printf("%d\n",i / j);
            else{
                printf("1\n");
        }
    }
    return 0;
}
/*abcd aaaa ababab 1 4 3*/