lib-src/strings/kmp.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <stddef.h>
  26 #include <string.h>
  27 #include <AD/strings/kmp.h>
  28
  29 void KMP::compile (register const char * pattern, int len)
  30 {  delete [] skip; skip = NULL;
  31    if (len < 0) len = strlen(pattern);
  32    if ( (patternLength = len) > 0) {
  33       register int i, w, c;
  34
  35       //
  36       //  ps[i] = Given a prefix |w| of pattern with length i,
  37       //          the length of the proper prefix of |w|
  38       //          that is also a suffix of |w|
  39       //
  40       skip = new Skip [patternLength];
  41       register int * ps = new int [patternLength];
  42
  43       ps[0] = 0;
  44       for (i = 1; i < patternLength; i++) {
  45          for (w = ps[i-1]; ; w = ps[w-1] ) {
  46             if (pattern[i] == pattern[w]) { ps[i] = w + 1; break; }
  47             if (w == 0) { ps[i] = 0; break; }
  48          }
  49       }
  50
  51       for (c = 0; c < 256; c++) skip[0][c] = 1;
  52       skip[0][(unsigned char)pattern[0]] = 0;
  53
  54       //
  55       // skip[i][c] = 0   if  pattern[i] == c
  56       // skip[i][c] = i + 1 - ps( pattern[0 ... i-1] . c )
  57       //
  58       for (i = 1; i < patternLength; i++) {
  59          for (c = 0; c < 256; c++) {
  60             if (c == pattern[i]) skip[i][c] = 0;
  61             else { w = ps[i-1]; skip[i][c] = i - w + skip[w][c]; }
  62          }
  63       }
  64
  65       delete [] ps;
  66    }
  67 }
  68
  69 int KMP::Match(register const char * text, int textLength) const
  70 {  if (textLength < 0) textLength = strlen(text);
  71    register int m, p;  // characters matched and text position
  72    register int patLen = patternLength;
  73    register int limit = textLength - patLen;
  74    for (m = 0, p = 0; p <= limit; ) {
  75       if (m == patLen) return p;
  76       register int d = skip [ m ] [ text [m + p] ];
  77       p += d; m += 1 - d;
  78    }
  79    return -1;
  80 }