写在前面

表示的子串.
这里的下标从1开始.
i的上一个匹配:一个位置j,满足.
下面黑线表示字符串,其中红框中包含的字符相等(这是自然，同一个字符串嘛).

j还要满足

(注意啦 两条黑线表示同一个字符串，只是位置不同)
(其实这也算是KMP的复习吧...)
下面图中红框中都表示相同.

算法

KMP.由于这不是KMP学习笔记,不仔细讲,请先学会KMP.

思路

这题也可算是"拍大腿"系列了吧?其实你看看下面代码,真的很简单,关键就是如何推出这个结论.
(我不用next/fail,用了f做数组名,希望大家不要看不习惯,意思是一样的)

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

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

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

代码

#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;
}