我们考虑KMP算法中fail失配指针的意义。
对于一个模式串（Pattern），位置i对应的失配指针fail[i]是那个位置：
这个位置满足的条件是，子串[0, fail[i])是位置i（不含）的后缀，并且fail[i]是所有满足此条件的位置中最靠后（最接近i）的那个。
也就说当我们用模式串P匹配文本串T的时候，我们检查当前位置T[i]与P[j]是否匹配,
若匹配i,j指针各向前移动一位；
否则,利用模式子串[0, j)与文本子串i（不含）的后缀已经匹配的信息，保持i指针不变，j指针退到fail[j]位置再次尝试匹配。
退回的指针位置同样应该满足P的前缀与i（不含）后缀相匹配。
那么一个模式串fail指针蕴含着当前位置后缀与模式串前缀匹配的信息。
回到本题，考虑位置i(>0)，若i位置是某个重复节(长度设为len)的终点，那么其失配指针必然指向(i - len)位置，
并且满足len | (i + 1) && str[i - len] == str[i]。
反之我们有满足此条件的必然是某个重复节的终点：
因为[0, fail[i]]可用字符串拼接表示：s1 + s2 + ... + sk + t，其中strlen(si) = len,
那么[len, i]必然是s2 +... + sk + t + t。
有s1 = s2 && s2 == s3 &&... && sk -1 = sk && sk = t。
可见该条件对于所求是等价的。
http://poj.org/problem?id=1961
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + ;
char str[maxn];
int n;
int fail[maxn]; int main(){
//freopen("in.txt", "r", stdin);
int kase = ;
while(~scanf("%d", &n) && n){
char ch, *p = str;
while((ch = getchar()) != '\n') ch = getchar();
for(int i = ; i < n; i++) *(p++) = getchar();
fail[] = fail[] = ;
for(int i = ; i < n; i++){
//compute forward not backward
int j = fail[i];
while(j && str[j] != str[i]) j = fail[j];
fail[i + ] = str[j] == str[i] ? j + : ;
}
printf("Test case #%d\n", ++kase);
for(int i = ; i < n; i++){
int delta = i - fail[i];
if((i + ) % delta == && str[i] == str[fail[i]]){
printf("%d %d\n", i + , (i + ) / delta);
}
}
putchar('\n');
}
}