kmp.c

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