Skip to content

Instantly share code, notes, and snippets.

@behitek
Forked from osjayaprakash/kmp.cpp
Created November 17, 2018 02:13
Show Gist options
  • Save behitek/04c8be5a4cad5a96c6f6b4969fbd63e2 to your computer and use it in GitHub Desktop.
Save behitek/04c8be5a4cad5a96c6f6b4969fbd63e2 to your computer and use it in GitHub Desktop.
KMP
#include <iostream>
#include <cstring>
using namespace std;
int buildlps (char * pat, int m, int *lps){
lps[0] = lps[1] = 0;
for(int i=2; i<=m; i++){
int j = lps[i-1];
while(1){
if( pat[ j ] == pat[ i-1 ] ){ // progress
lps[i] = j + 1;
break;
}
if(j<=0) { // avoid dead-end loops & first mismatch
lps[i] = 0;
break;
}
j = lps[j]; // failure in current state, fallback again
}
}
}
int search(char * s, chat *p, int n, int m){
int lps[] = new int[m+1];
int si, pi; //string index, pattern index
buildlps(p, m, lps);
for( si = pi = 0; si<n; ){
if( s[si] == p[pi] ){ // progress
si++;
pi++;
if(pi == m){
cout << "found" << endl;
break;
}
}else{
if(pi == 0) //first mismatch
si++;
else{
pi = lps[pi]; // fall back
}
}
}
}
int main(){
char s[] = "ababababac";
char p[] = "ababac";
int n = strlen(s);
int m = strlen(p);
search(s, p, n, m);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment