kmp.c

   1 #include "code.h"
   2
   3 int kmpNext[128];
   4
   5 void prep_kmp()
   6 {
   7         int i, j;
   8
   9         i = 0;
  10         j = kmpNext[0] = -1;
  11
  12         while (i < m) {
  13                 while (j > -1 && pattern2[i] != pattern2[j])
  14                         j = kmpNext[j];
  15                 i++;
  16                 j++;
  17
  18         if (pattern2[i] == pattern2[j])
  19                  kmpNext[i] = kmpNext[j];
  20         else
  21               kmpNext[i] = j;
  22    }
  23 }
  24
  25
  26 unsigned int search_kmp()
  27 {
  28         prep_kmp();
  29
  30         unsigned int i, j, matches = 0;
  31
  32         i = j = 0;
  33         while (i < n * n) {
  34                 while (j > -1 && pattern2[j] != text2[i])
  35                         j = kmpNext[j];
  36
  37                 i++;
  38                 j++;
  39
  40                 if (j == m) {
  41                         matches++;
  42                         j = kmpNext[j];
  43                 }
  44         }
  45         return matches;
  46 }
  47