git.maemo.org Git - mstardict/blob - src/lib/kmp.cpp

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "kmp.h"
   6
   7 static int* prefix = NULL;
   8 static int max_size = 0;
   9
  10 static void GetPrefixValue(const char* strPattern, int iPatternLen)
  11 {
  12     if (iPatternLen>max_size) {
  13         prefix = (int*)realloc(prefix, iPatternLen*sizeof(int));
  14         max_size = iPatternLen;
  15     }
  16
  17     int i, j; /* i runs through the string, j counts the hits*/
  18     i = 1; j = 0;
  19     prefix[0] = 0;
  20
  21     while(i<iPatternLen)
  22     {
  23         if(strPattern[i] == strPattern[j])
  24         {
  25             prefix[i] = ++j;
  26         }
  27         else
  28         {
  29             j = 0;
  30             prefix[i] = j;
  31         }
  32
  33         i++;
  34     }
  35 }
  36
  37 static int KMPStringMatch(const char* strPattern, int iPatternLen, const char* strTarget, int iTargetLen)
  38 {
  39         int j =0;
  40         int i;
  41         for (i=0;i<iPatternLen;i++) {
  42                 while ((strPattern[i] != strTarget[j]) && (j > 0))
  43                         j = prefix[j-1];
  44                 if (strPattern[i] == strTarget[j])
  45                         j++;
  46                 if (j == iTargetLen)
  47                         return i - j + 1;
  48         }
  49         return -1;
  50 }
  51
  52 int KMP(const char* strPattern, int len, const char* strTarget)
  53 {
  54         GetPrefixValue(strPattern, len);
  55         return KMPStringMatch(strPattern, len, strTarget, strlen(strTarget));
  56 }
  57
  58 void KMP_end()
  59 {
  60         free(prefix);
  61         prefix=NULL;
  62         max_size=0;
  63 }