KMP

kmp.cpp

#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);
}