Knuth-Morris-Pratt algorithm

/*
* Status: Tested OK
* Title: Knuth-Morris-Pratt algorithm
* Category: String matching
* Difficulty Level: Medium
* Name: Akshay Thakare
*/

/*
Functions involved
1. Overlap
2. KMP
*/

/*
Debug procedure
1. Main
2. Overlap
3. KMP
*/

#include 
#include 
#include 

#define T_SZ 100		//Text string array size
#define P_SZ 10		//Pattern string array size

char txt[T_SZ];			//Text string
int n;				//Length of text string
char pat[P_SZ];			//Pattern String
int m;				//Length of pattern string

int o_lap[P_SZ];

void overlap();
void KMP();

int main()
{
	printf("\n----------KMP----------\n");
	printf("\nEnter the text string to be searched in = ");
	scanf("%s",txt);
	
	printf("\nEnter the pattern string to be searched = ");
	scanf("%s",pat);

	n = strlen(txt);	
	m = strlen(pat);	

	overlap();
	KMP();
	
	printf("\n");
}

void overlap()
{
	int k;			//Position of start of the matched string
	char c;			//Current character
	int v;			//Last overlap value
	
	o_lap[0]=0;
	o_lap[1]=0;
	
	for(k=1;k=m)
	{
		while(jm)
		{
			printf("\nString found starting from position = %d",k);
		}
		
		if((o_lap[j-1])>0)
		{
			k = i - o_lap[j-1];
		}
		else
		{
			if(i==k)
			{
				i++;
			}
			k=i;
		}
		
		if(j>1)
		{
			j = o_lap[j-1]+1;
		}
	}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s