当初学KMP的时候也做过这道题，现在看来还是刘汝佳的代码要精简一些，毕竟代码越短越好记，越不容易出错。
而且KMP的递推失配函数的代码风格和后面的Aho-Corasick自动机求失配函数的代码风格也是一致的。
#include <cstdio> const int maxn = + ;
char s[maxn];
int f[maxn]; //失配函数 int main()
{
//freopen("in.txt", "r", stdin); int n, kase = ;
while(scanf("%d", &n) == && n)
{
getchar();
for(int i = ; i < n; i++) s[i] = getchar(); //递推求解失配函数
f[] = f[] = ;
for(int i = ; i < n; i++)
{
int j = f[i];
while(j && s[i] != s[j]) j = f[j];
f[i+] = s[i] == s[j] ? j+ : ;
} printf("Test case #%d\n", ++kase);
for(int i = ; i <= n; i++)
if(f[i] && i % (i - f[i]) == )
printf("%d %d\n", i, i / (i - f[i]));
printf("\n");
} return ;
}
代码君