LOGIC
- Read the pattern and text
- Compute failure function
- Apply the KMP algorithm
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computefailure(char *pat, int M, int *f);
void KMPSearch(char *pat, char *txt) //to implement kmp search {
int M = strlen(pat);//length of pattern
int N = strlen(txt);//length of text
int *f = (int *)malloc(sizeof(int)*M); //dynamic allocation int j = 0; // index for pat[]
computefailure(pat, M, f);
int i = 0; // index for txt[]
while(i < N)
{
if(pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = f[j-1];
}
else if(pat[j] != txt[i])
{
if(j != 0)
j= f[j-1];
else
i = i+1;
}
}
free(f);
}
void computefailure (char *pat, int M, int *f) //compute the failure function {
int len = 0;
int i;
f[0] = 0; // f[0] is always 0
i = 1;
while(i < M)
{
if(pat[i] == pat[len])
{
len++;
f[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if( len != 0 )
{
len = f[len-1];
}
else // if (len == 0)
{
f[i] = 0;
i++;
}
}
}
}
int main()
{
int match;
printf("\nEnter the Text: ");
gets(text); //reading the text
printf("\nEnter the Pattern: ");
gets(pattern); //reading the pattern
m=strlen(text);
n=strlen(pattern);
match=KMPSearch(pat, txt);
if(match>=0)
{
printf("\nMatch found at position %d\n\n",match);
}
else
{
printf("\nNo Match found!!!\n\n");
}
return 0;
}