I wrote this code and it works in some cases. Sometimes, however, it fails, and I just can't see why. Can someone please help me spot the error?
It works for:
String: ishanthakkar ishan
patter: ishan
But it fails for:
String: cpr ograming
patter: cpr
Source:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int *compute_prefix_function(char *pattern, int psize)
{
int k = -1;
int i = 1;
int *pi = malloc(sizeof(int)*psize);
if (!pi)
return NULL;
pi[0] = k;
for (i = 1; i < psize; i++) {
while (k > -1 && pattern[k+1] != pattern[i])
k = pi[k];
if (pattern[i] == pattern[k+1])
k++;
pi[i] = k;
}
return pi;
}
// This function find matching string in O(n) time, so iterate through text string only once, when unmatching character found; it proceed with next character and start comparing with first character of string to be searched i.e pattern
int kmp(char *target, int tsize, char *pattern, int psize)
{
int i;
int *pi = compute_prefix_function(pattern, psize);
int k = -1;
if (!pi)
return -1;
for (i = 0; i < tsize; i++) {
while (k > -1 && pattern[k+1] != target[i])
k = pi[k];
if (target[i] == pattern[k+1])
k++;
if (k == psize - 1) {
free(pi);
return i-k;
}
}
free(pi);
return -1;
}
int main(int argc, const char *argv[])
{
char target[200];
char *ch = target;
char pattern[20];
int i;
printf("Enter the string: \n");
fgets(target,100,stdin);
printf("Enter the string to be matched: \n");
fgets(pattern,20,stdin);
i = kmp(target, strlen(target), pattern, strlen(pattern));
if (i >= 0)
printf("matched @: %s\n", ch + i);
getch();
return 0;
}
kmp()
is not part of the standard computing lexicon as far as I know, and you only state that the program does "pattern matching" without ever specifying what that means. For all we know, the code could be correct as posted.kmp
is unambiguously Knuth-Morris-Pratt in string algorithms.