home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / BMHSRCH.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  2KB  |  71 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /*
  4. **  Case-sensitive Boyer-Moore-Horspool pattern match
  5. **
  6. **  public domain by Raymond Gardner 7/92
  7. **
  8. **  limitation: pattern length + string length must be less than 32767
  9. **
  10. **  10/21/93 rdg  Fixed bug found by Jeff Dunlop
  11. */
  12. #include <limits.h>                                         /* rdg 10/93 */
  13. #include <stddef.h>
  14. #include <string.h>
  15.  
  16. typedef unsigned char uchar;
  17.  
  18. #define LARGE 32767
  19.  
  20. static int patlen;
  21. static int skip[UCHAR_MAX+1];                               /* rdg 10/93 */
  22. static int skip2;
  23. static uchar *pat;
  24.  
  25. void bmh_init(const char *pattern)
  26. {
  27.           int i, lastpatchar;
  28.  
  29.           pat = (uchar *)pattern;
  30.           patlen = strlen(pattern);
  31.           for (i = 0; i <= UCHAR_MAX; ++i)                  /* rdg 10/93 */
  32.                 skip[i] = patlen;
  33.           for (i = 0; i < patlen; ++i)
  34.                 skip[pat[i]] = patlen - i - 1;
  35.           lastpatchar = pat[patlen - 1];
  36.           skip[lastpatchar] = LARGE;
  37.           skip2 = patlen;                 /* Horspool's fixed second shift */
  38.           for (i = 0; i < patlen - 1; ++i)
  39.           {
  40.                 if (pat[i] == lastpatchar)
  41.                       skip2 = patlen - i - 1;
  42.           }
  43. }
  44.  
  45. char *bmh_search(const char *string, const int stringlen)
  46. {
  47.       int i, j;
  48.       char *s;
  49.  
  50.       i = patlen - 1 - stringlen;
  51.       if (i >= 0)
  52.             return NULL;
  53.       string += stringlen;
  54.       for ( ;; )
  55.       {
  56.             while ( (i += skip[((uchar *)string)[i]]) < 0 )
  57.                   ;                           /* mighty fast inner loop */
  58.             if (i < (LARGE - stringlen))
  59.                   return NULL;
  60.             i -= LARGE;
  61.             j = patlen - 1;
  62.             s = (char *)string + (i - j);
  63.             while (--j >= 0 && s[j] == pat[j])
  64.                   ;
  65.             if ( j < 0 )                                    /* rdg 10/93 */
  66.                   return s;                                 /* rdg 10/93 */
  67.             if ( (i += skip2) >= 0 )                        /* rdg 10/93 */
  68.                   return NULL;                              /* rdg 10/93 */
  69.       }
  70. }
  71.