# Knuth-Morris- Pratt pattern matching algorithm

Knuth-Morris- Pratt, pattern matching algorithm
Write a C program for implementing Knuth-Morris- Pratt pattern matching algorithm.

1. Algorithm for kmpSearch (char *str, char *word, int *ptr)
Step1: Declare & assign i = 0, j = 0
Step2: Repeat i+j until less than string upto 11

while ((i + j) < strlen(str))
Step3:Checking the match found on the target and pattern string char upto Step6
if (word[j] == str[i + j])
Step:4 Check upto Step5
if (j == (strlen(word) - 1))
Step5: Read the location of the index word, i + 1
return
Step6: j = j + 1
Step7: else otherwise check upto step manipulating next indices to compare
Step8: i = i + j - ptr[j];
Step 9: check j > -1
if (ptr[j] > -1)
Step10: j = ptr[j];
Step11: otherwise else j = 0;
Step12 stop

2. Algorithm to find the overlap array for the given pattern
findOverlap(char *word, int *ptr)
Step1: Start
Step2:Declare & assign i = 2, j = 0, len = strlen(word)
ptr[0] = -1 ptr[1] = 0
Step3: Repeate upto i less than length
while (i < len)
Step4: Check upto step7
if (word[i - 1] == word[j])
Step5: j = j + 1
Step6: ptr[i] = j
Step7: i = i + 1
Step8: otherwise check else if (j > 0)
Step9: j = ptr[j]
Step10: otherwise Check upto 12 else
Step11: ptr[i] = 0
Step12: i = i + 1
Step13: stop

3. Algorithm : main function
Step1: Start
Step2: Declare word[256], str[1024] *ptr, i
Step3: Read the target string from the user
Step4: Read the pattern string word from the user
Step5: dynamic memory allocation for overlap array
ptr = (int *)calloc(1, sizeof(int) * (strlen(word)))
Step6: call sub function overlap
findOverlap(word, ptr)
Step7: call the subfunction find the index of the pattern in target string
kmpSearch(str, word, ptr);
Step8: Stop

Thanks
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..