Skip to content

Instantly share code, notes, and snippets.

@hailangx

hailangx/kmp.cpp

Last active August 29, 2015 14:20
Show Gist options
  • Save hailangx/d1d01892e90c5ff0feb1 to your computer and use it in GitHub Desktop.
Save hailangx/d1d01892e90c5ff0feb1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @haiyangxu haiyangxu renamed this gist Apr 29, 2015. 1 changed file with 0 additions and 0 deletions.
    0 kmp → kmp.cpp
    View file
    File renamed without changes.
  2. @haiyangxu haiyangxu created this gist Apr 29, 2015.
    27 changes: 27 additions & 0 deletions kmp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,27 @@
    #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;
    }