kmp.cpp

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//compute the next arry for KMP
int nextp(string str,vector<int>&pi){
    str.insert(0,1,'@');// convert to 1 based index
    pi=vector<int>(str.size(),0);
    pi[0]=-1;pi[1]=0;
    for(int i=2;i<str.length();i++){
        if(str[pi[i-1]+1]==str[i])
            pi[i]=pi[i-1]+1;
        else pi[i]=0;
    }
    return 0;
}
int main(){
    string strs="ababababca";
    vector<int>pi;
    nextp(strs,pi);
    for(int i=0;i<pi.size();i++)
    {
        cout<<pi[i]<<" ";
    }
    return 0;
}