View Code of Problem 1046

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

const int maxn = 1000000+10;
int next[maxn];
int n;
string str;

vector<int> find(string T,string P){
    int n = T.size(),m = P.size();
    vector<int> vn;
    getNext(P,next);
    for(int i = 0,j = 0; i < n; i++){
        while(j&&P[j] != T[i]) j = next[j];
        if(P[i]==T[j]) j++;
        if(j==m) vn.push_back(i-m+1);
    }
    return vn;

}

void getFail(string st,int *f){
    int m = st.size();
    next[0] = 0;
    next[1] = 0;
    int len = 1;
    for(int i = 1; i < m; i++){
        int j = next[i];
        while(j && st[i] != st[j]) j = next[j];
        if(st[i]==st[j]){
            next[i+1] = j+1;
        }else{
            next[i+1] = 0;
        }
    }
}
int main(){
    int T = 1;
    while(~scanf("%d",&n) && n){
        cin >> str;
        printf("Test case #%d\n",T++);
        getFail(str,next);
        for(int i = 2; i <=  n; i++){
            if(next[i]> 0&&i%(i-next[i])==0){
                cout<<i<<" "<<i/(i-next[i])<<endl;
            }
        }
        cout<<endl;
    }
    return 0;
}

/*
F:\temp\16139661.54678\Main.cc: In function 'std::vector<int, std::allocator<int> > find(std::string, std::string)':
F:\temp\16139661.54678\Main.cc:20: error: 'getNext' was not declared in this scope
*/