Skip to content

Instantly share code, notes, and snippets.

@liuqinh2s liuqinh2s/KMP.cpp
Last active Aug 8, 2016

Embed
What would you like to do?
int KMP(Str str, Str substr, int next[]){
int i=0,j=0;
while(i<str.length && j<substr.length){
if(j==-1||str.ch[i] == substr.ch[j]){
++i;
++j;
}
else{
j=next[j];
}
}
if(j==substr.length){
return i-substr.length;
}
else return -1;
}
void getnext(Str substr, int next[]){
int i=0,j=-1;
next[0]=-1;
while(i<substr.length-1){
if(substr.ch[i]==substr.ch[j]){
++i;
++j;
next[i] = j;
}
else{
j=next[j];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.