code

Morris Pratt

The Morris Pratt algorithm
mp.c

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

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

   /* Preprocessing */
   preMp(x, m, mpNext);

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