这道KMP入门，主要在于加深next函数的理解，即与自身的匹配。
#include<iostream>
#include<vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <math.h>
#include<algorithm>
#define ll long long
#define eps 1e-8
using namespace std; int nexts[];
char str[]; void pre_nexts(int n)//next函数
{
memset(nexts,,sizeof(nexts));
int j = ,k = -;
nexts[] = -;
while(str[j])
{
if(k == - || str[j] == str[k]) nexts[++j] = ++k;//与自身的子串匹配
else k = nexts[k];//匹配失败，返回
}
}
void KMP()
{
int i,t;
for(i = ; str[i-]; i++)
{
t = i - nexts[i];//子串长度
if(i % t == && i / t > ) printf("%d %d\n",i,i/t);//如果当前位置为一个循环节，則输出
}
}
int main(void)
{
int n,cnt = ;
while(scanf("%d",&n),n)
{
scanf("%s",str);
pre_nexts(n);
printf("Test case #%d\n",cnt++);
KMP();
printf("\n");
}
return ;
}