传送： http://poj.org/problem?id=2406
题意：给定一个字符串，让你求出他最多由几个相同的连续子串连接而成。
KMP的一些小知识点：
如果对于next数组中的 i， 符合 i % ( i - next[i] ) == 0 && next[i] != 0 , 则说明字符串循环，而且
循环节长度为: i - next[i]
循环次数为: i / ( i - next[i] )
#include <stdio.h> #include <cstring> #define N 1000010 char s[N]; int next[N]; int len; void kmp()/* 可以作为KMP的模板 */ { int i = 0, j = -1; next[0] = -1; while(i < len) { if(j == -1 || s[i] == s[j]) { i++; j++; next[i] = j; } else j = next[j]; } } int main() { while(~scanf("%s", &s)) { memset(next, 0, sizeof(next)); if(s[0] == ‘.‘) break; len = strlen(s); kmp(); int sum = 1; if(len % (len - next[len]) == 0) sum = len / (len - next[len]); printf("%d\n", sum); } return 0; }
原文：http://www.cnblogs.com/yu0111/p/4838754.html