深入理解KMP，是next数组的应用

#include <iostream>
#include <stack>

using namespace std;

const int N = 1000000;

int ne[N];

void getnext(string p){
    int m = p.size();
    int j = 0, k = -1;
    ne[j] = k;
    while(j < m){
        if(k == -1 || p[j] == p[k]){
            j++;
            k++;
            ne[j] = k;
        }else{
            k = ne[k];
        }
    }
}

int main(){
    int t = 1, n;
    string s;
    while(cin >> n){
        if(n == 0) break;
        cin >> s;
        printf("Test case #%d\n", t++);
        getnext(s);
        for(int i = 0; i <= n; i++){
            int t = i - ne[i];
            if(i % t == 0 && i / t >= 2){
                printf("%d %d\n", i, i / t);
            }       
        } 
        printf("\n");
    }
    return 0;
}