LINK

UVA1328
luogu remote judge UVA1328
poj1961

写在前面

Substr(i, j)表示s的子串s[i~j]

这里s的下标从1开始

i的上一个匹配：一个位置j,满足Substr(1, j) == Substr(i - j + 1,N)

下面黑线表示字符串，其中红框中包含的字符相等（这是自然，同一个字符串嘛）。

j还要满足

（注意啦 两条黑线表示同一个字符串，只是位置不同）

（其实这也算是KMP的复习吧。。。）

下面图中红框中都表示相同

思路

你看看下面代码,真的很简单,关键就是如何推出这个结论.
(我不用next,用了f做数组名,希望大家不要看不习惯,意思是一样的)

粉色部分也表示相同。这很明显，因为字符是一一对应的嘛(同一个字符串位置相同、长度相同的字符串当然一样)。
由于红框内完全相同，还可以——

继续对应!灰线表示在原字符串中是对应的.
还可以对应!

可能就会出现这样的情况!(当然可能最前面不够长度)
因此，只要f[i]>0，i前面肯定有循环节!(只不过不知道是否完整,bb|abb|abb|abb这样也看作是)而且循环节长度为i - f[i] + 1.因此只要判断循环节长度能否将长度整除即可.具体请见代码(真的短).

代码

#include<cstdio>
using namespace std;
#define MAXN 1000005

int N, T;
char s[MAXN];
int f[MAXN];

int main(){
    while( ~scanf( "%d", &N ) && N ){
        scanf( "%s", s + 1 ); T++;
        printf( "Test case #%d\n", T );
        int t(0); f[1] = 0;
        for ( int i = 2; i <= N; ++i ){
            while ( s[i] != s[t + 1] && t ) t = f[t];
            if ( s[i] == s[t + 1] ) t++;
            f[i] = t;
            if ( f[i] != 0 && i % ( i -  f[i] ) == 0 ) printf( "%d %d\n", i, i / ( i - f[i] ) );
        }
        putchar('\n');
    }
    return 0;
}