Knuth–Morris–Pratt Algorithm

Knuth–Morris–Pratt.cpp

/*
KMP (Knuth–Morris–Pratt algorithm) is a nice algorithm for solving some string matching 
problems (match a pattern in a text).  CLRS book devotes a subsection for describing the 
KMP algorithm in detail. KMP leverages the longest prefix of P that is also a proper suffix 
of a string pattern to avoid redundent computations. The information is precomputed and 
represented in an  rray named prefix function, which indicates how much we should shift after 
have matched successfully at a particular shift s in the text.      
  
KMP is beautiful!  You are gonna understand it!
*/ 
//Now it's time for the actual implementation:
#include <iostream>

class KMP
{
public:
  KMP(void);
	~KMP(void);
	static int *getPrefixFunction(char *str); 
	static bool KMPMatch(char *text, char *pattern);
};

KMP::KMP(void)
{
}


KMP::~KMP(void)
{
}

int* KMP::getPrefixFunction(char *str)
{
  if(!str)
		return NULL;
	int n=strlen(str);
	int k=0;
	int *A = new int[n];
	A[0] = 0;
	for(int i=1; i<n; i++){
		while(k&&str[k]!=str[i])  //this loop is to find the k-1
			k = A[k-1];          //The condition str[k]!=str[i] makes sure it finds 
		if(str[i]==str[k])
			k = k+1;
		A[i] = k;
	}
	return A;
}

bool KMP::KMPMatch(char *text, char *pattern)
{
	if(!pattern) return true;
	if(!text) return false;
	int n = strlen(text);
	int p = strlen(pattern);
	int *sf = getPrefixFunction(pattern);
	int localMatch = 0;
	for(int i=0; i<=n-p; i++){
		for(int j=localMatch, k=0; j<p; j++,k++){
			if(text[i+k]==pattern[j])
				localMatch++;
			else{
				localMatch = sf[localMatch];
				i=i+(localMatch-sf[localMatch])+sf[localMatch]; //I previous put this before the above statement.
				break;
			}
		}
		if(localMatch==p)
			return true;
	}
	return false;
}