Skip to content

Instantly share code, notes, and snippets.

@calmhandtitan
Created December 9, 2013 13:40
Show Gist options
  • Save calmhandtitan/7872383 to your computer and use it in GitHub Desktop.
Save calmhandtitan/7872383 to your computer and use it in GitHub Desktop.
C implementation of Knuth Morris Pratt Algorithm for pattern searching in linear time
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void computeLPSarray(char *pat, int M, int *lps)
{
int len = 0; //lenght of previous longest prefix suffix
int i ;
lps[0] = 0 ; //lps[0] is always 0
i = 1;
while(i < M) //loop calculates lps[i] for i = 1 to M-1
{
if(pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else //pat[i] != pat[len]
{
if(len != 0)
{
//this is tricky
//consider the example AAACAAAA and i =7
len = lps[len - 1];
//we donot increment i here
}
else //if len == 0
{
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
int *lps = (int*)malloc(M*sizeof(int));
int j = 0;
computeLPSarray(pat, M, lps);
int i = 0;
while(i < N)
{
if(pat[j] == txt[i])
{
j++;
i++;
}
if(j == M)
{
printf("Found pattern at index %d\n",i - j);
j = lps[j-1];
}
else if(pat[j] != txt[i])
{
if(j != 0)
j = lps[j-1];
else
i++;
}
}
free(lps);
}
int main()
{
char *txt = "ABABDABACDABDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
@ArchitKumar1
Copy link

Code doesnt work

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment