详细请查看注释

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, ne[N];
char s[N];

/*
    KMP：
        对于具有循环节性质的字符串，它的next数组有一个性质：
            s[1 ~ next[i]] == s[i-next[i]+1 ~ i] 一定相等且最大！
            循环节长度就是：i / (i - next[i])

        s[1 ~ n]具有t < i长度循环节的充要条件是：前缀等于后缀, 即 s[1 ~ n-t] == s[t+1 ~ n]
            证明：
                充分性：若是字符串循环节长度为t，则前缀等于后缀s[1 ~ n-t] == s[t+1 ~ n]
                    这个是显然的！
                比要性：若一个字符串前缀等于后缀，即 s[1 ~ n-t] == s[t+1 ~ n]，则该字符串的循环节长度为t
                    对于这个可以画个图来看：下方序列是上方的复制！
                        (---.---.---.---.---.---.---.---.)---
                          | \ | \ | \ | \ | \ | \ | \ | \ |
                        ---.(---.---.---.---.---.---.---.---)

                    如图所示：由于条件是上面括号等于下面括号，因此括号对应相等，中间线对应的都相等
                        证得：循环节长度为 t 

            本题求最短的循环节t：即t最小，也就是n - t最大  ---> 也就是前缀和后缀相等且最大，这就是next数组的含义！
                则 n - next[n]就是循环节t最短时的最大长度！

        当i - next[i]能够整除i时候,那么s[1 ~ i-next[i]]就是s[1 ~ i]的最小循环元, 次数是：i / (i - next[i]).
*/

int main(){
    int T = 1;
    while(cin >> n, n){
        cin >> s + 1;
        for(int i = 2, j = 0; i <= n; i ++){
            while(j && s[i] != s[j + 1]) j = ne[j];
            if(s[i] == s[j + 1]) j ++;
            ne[i] = j;
        }
        cout << "Test case #" << T ++ << endl;
        for(int i = 1; i <= n; i ++){
            int t = i - ne[i];
            if(i % t == 0 && i / t > 1) cout << i << " " << i / t << endl;
        }
        cout << endl;
    }
    return 0;
}