• • KMP (Knuth–Morris–Pratt) is a string searching algorithm which runs in O(m + n) time, where m is the length of the pattern and n is the length of the text to be searched.

Problem: Find the first (or all) instances of the pattern in the text. for example below figure explains in simple way…….. ## How to implement KMP algorithm in C program:

KMP algorithm is done in two steps. They are finding the overlap in the pattern and finding pattern in target string.

```/**************************************************************************/
//sample code
/*************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*
* finds the position of the pattern in the given target string
* target - str, patter - word
*/
int kmpSearch( char *str, char *word,int *ptr)
{
int i = 0, j = 0;

while ((i + j) < strlen (str))
{
/* match found on the target and pattern string char */
if (word[j] == str[i + j])
{
if (j == (strlen (word) - 1))
{
printf ("%s located at the index %d\n", word, i + 1);
return;
}
j = j + 1;
}
else
{
/* manipulating next indices to compare */
i = i + j - ptr[j];
if (ptr[j] > -1)
{
j = ptr[j];
}
else
{
j = 0;
}
}
}
}

/* find the overlap array for the given pattern */
void
findOverlap (char *word, int *ptr)
{
int i = 2, j = 0, len = strlen (word);

ptr = -1;
ptr = 0;

while (i < len)
{
if (word[i - 1] == word[j])
{
j = j + 1;
ptr[i] = j;
i = i + 1;
}
else if (j > 0)
{
j = ptr[j];
}
else
{
ptr[i] = 0;
i = i + 1;
}
}
return;
}

int
main ()
{
char word, str;;
int *ptr, i;

/* get the target string from the user */
fgets (str, 1024, stdin);
str[strlen (str) - 1] = '\0';

/* get the pattern string from the user */
fgets (word, 256, stdin);
word[strlen (word) - 1] = '\0';

/* dynamic memory allocation for overlap array */
ptr = (int *) calloc (1, sizeof (int) * (strlen (word)));

/* finds overlap array */
findOverlap (word, ptr);
/* find the index of the pattern in target string */
kmpSearch (str, word, ptr);

return 0;
}
```