lib-src/strings/bm.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/bm.h>
  28
  29 BoyerMoore::~BoyerMoore() { delete [] ps; delete [] pat; }
  30
  31 BoyerMoore::BoyerMoore(const char * pattern) : ps(0), pat(0)
  32 { *this = pattern; }
  33
  34 void BoyerMoore::compile (const char * pattern, int len)
  35 {   delete [] ps; delete [] pat; ps = NULL; pat = NULL;
  36     if (len < 0) len = strlen(pattern);
  37     if ( (patternLength = len) > 0) {
  38        register int i, w, c;
  39
  40        pat = new char [patternLength];
  41        memcpy(pat,pattern,patternLength);
  42        ps = new int [patternLength];
  43
  44        //
  45        // ps[i] = let p = pattern[i ... n-1]
  46        //         the length of the largest proper nonempty prefix of p that
  47        //             is also the proper nonempty suffix of p.
  48        ps[patternLength-1] = 0;
  49        for (i = patternLength - 2; i >= 0; i--) {
  50           for (w = ps[i+1]; ; w = ps[patternLength-w]) {
  51              if (ps[i] == pattern[patternLength - w - 1])
  52                 { ps[i] = w + 1; break; }
  53              if (w == 0) { ps[i] = 0; break; }
  54           }
  55        }
  56        for (i = patternLength - 2; i >= 0; i--)
  57           ps[i] = patternLength - ps[i];
  58
  59
  60        //
  61        // last[c] = the last offset(from right) of c in pattern
  62        //           or the length of the pattern if none such c exists.
  63        //
  64        for (c = 0; c < 256; c++) last[c] = patternLength;
  65        for (i = 0; i < patternLength - 1; i++)
  66           for (c = 0; c < 256; c++)
  67              if (pattern[i] == c) last[c] = patternLength - 1 - i;
  68     }
  69 }
  70
  71 int BoyerMoore::Match(register const char * text, int length) const
  72 {  if (length < 0) length = strlen(text);
  73    register int limit = length - patternLength;
  74    register int pos;
  75    for ( pos = 0; pos <= limit; ) {
  76       register int i;
  77       for (i = patternLength - 1; i >= 0 && pat[i] == text[pos + i]; i--);
  78       if (i < 0) return pos;
  79       register int x = last[text[pos+i]];
  80       register int y = ps[i];
  81       if (x > y) pos += x; else pos += y;
  82    }
  83    return -1;
  84 }