Aim:

Write a program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt

Solution :

C program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt

#include <stdio.h>
#include <string.h>

int lps[100];
void longestPrefixSuffix(char p[])
{
	int i=1,j=0;
	int m = strlen(p);
	lps[0] = 0;
	while(i < m)
	{
		if( p[j] == p[i])
		{
			lps[i]=j+1;
			i++;
			j++;
		}
		else if(j>0)
			j = lps[j-1];
		else
		{
			lps[i]=0;
			i++;
		}
	}
}

int kmp (char p[],char t[])
{
	int n,m;
	int i=0,j=0;
	n = strlen(t);
    m = strlen(p);
	longestPrefixSuffix(p);
	while( i < n )
	{
		if ( p[j] == t[i])
		{
			if (j == m-1 ) 
				return i-j;
			i++; 
			j++;
		}
		else if(j>0)
			j = lps[j-1];
		else 
			i++;
	}
	return 0;
}

int main() {
   char t[]="kiss*miss*in*mississippi";
   char p[]="missi";
   int i;
   i=kmp(p,t);
   if(i)
		printf("pattern is present in text at position %d",i+1);
   else
		printf("pattern is not present in text");
   return 0;
}

pattern is present in text at position 14

Related Content :

Data Structures Lab Programs

1) Write a program that uses functions to perform the following operations on singly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

2) Write a program that uses functions to perform the following operations on doubly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

3) Write a program that uses functions to perform the following operations on circular linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

4) Write a program that implement Stack (its operations) using Array View Solution

5) Write a program that implement Stack (its operations) using Linked List (Pointer) View Solution

6) Write a program that implement Queue(its operations) using Array View Solution

7) Write a program that implement Queue (its operations) using Linked List (Pointer) View Solution

8) Write a program that implements Quick sort sorting methods to sort a given list of integers in ascending order View Solution

9) Write a program that implements Merge sort sorting methods to sort a given list of integers in ascending order View Solution

10) Write a program that implements Heap sort sorting methods to sort a given list of integers in ascending order View Solution

11) Write a program to implement the tree traversal methods using Recursive View Solution

12) Write a program to implement the tree traversal methods using Non Recursive View Solution

13) Write a program to implement Binary Search Tree (its operations) View Solution

14) Write a program to implement AVL Tree (its operations) View Solution

15) Write a program to implement Red - Black Tree (its operations) View Solution

16) Write a program to implement B Trees (its operations) View Solution

17) Write a program to implement B+ Trees (its operations) View Solution

18) Write a program to implement the graph traversal methods (Breadth First Search) View Solution

19) Write a program to implement the graph traversal methods (Depth First Search) View Solution

20) Write a program to Implement a Pattern matching algorithms using Boyer- Moore View Solution

21) Write a program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt View Solution