Pattern Searching - KMP algorithm

test1.cpp

#include <iostream>
#include <string>

using namespace std;

void kmp_search(string haystack, string needle){
	int N, M, i, j, len;
	N = haystack.length();
	M = needle.length();
	// Longest Proper Suffix array  or Partial match Table
	int LPS[M];
	LPS[0] = 0;
	len = 0;
	i = 1;
	// Construct the LPS array
	while(i < M){
		if(needle[i] == needle[len]){
			len += 1;
			LPS[i] = len;
			i += 1;
		}
		else{
			if(len == 0){
				LPS[i] = 0;
				i += 1;
			}
			else{
				len = LPS[len-1];
			}
		}
	}
	// Comparing each character
	i = 0;
	j = 0;
	while(i <= N-M){
		while(j < M){
			// If match occurs, keep matching
			if(haystack[i+j] != needle[j]){
				break;
			}
			j += 1;
		}
		// If mismatch occurs at first character
		if(j == 0){
			i += 1;
		}
		// If mismatch occurs at any other character
		else if(j < M){
			i += j - LPS[j-1];
			j = LPS[j-1];
		}
		// If all characters match in the pattern
		else{
			cout<<"Pattern found at index "<<i<<endl;
			i += j - LPS[j-1];
			j = LPS[j-1];
		}
	}
}

int main(){
	string haystack, needle;
	haystack = "foofoofoobar";
	needle = "foobar";
	kmp_search(haystack, needle);
	return 0;
}