code

Knuth Morris-Pratt

The Knuth Morris-Pratt algorithm
kmp.c

void preKmp(unsigned char *x, int m, int kmpNext[]) {
   int i, j;
   i = 0;
   j = kmpNext[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = kmpNext[j];
      i++;
      j++;
      if (i<m && x[i] == x[j])
         kmpNext[i] = kmpNext[j];
      else
         kmpNext[i] = j;
   }
}


int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, kmpNext[XSIZE], count;

   /* Preprocessing */
   preKmp(x, m, kmpNext);

   /* Searching */
   count = 0;
   i = j = 0;
   while (j < n) {
      while (i > -1 && x[i] != y[j])
         i = kmpNext[i];
      i++;
      j++;
      if (i >= m) {
         OUTPUT(j - i);
         i = kmpNext[i];
      }
   }
   return count;
}