home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #1 / monster.zip / monster / PROG_C / SNIP9404.ZIP / PBMSRCH.C < prev    next >
C/C++ Source or Header  |  1994-04-03  |  3KB  |  96 lines
  1. /*
  2. **        A Pratt-Boyer-Moore string search, written by Jerry Coffin
  3. **  sometime or other in 1991.  Removed from original program, and
  4. **  (incorrectly) rewritten for separate, generic use in early 1992.
  5. **  Corrected with help from Thad Smith, late March and early
  6. **  April 1992...hopefully it's correct this time. Revised by Bob Stout.
  7. **
  8. **  This is hereby placed in the Public Domain by its author.
  9. **
  10. **  10/21/93 rdg  Fixed bug found by Jeff Dunlop
  11. */
  12.  
  13. #include <stddef.h>
  14. #include <string.h>
  15. #include <limits.h>
  16.  
  17. static size_t table[UCHAR_MAX];
  18. static size_t len;
  19. static char *findme;
  20.  
  21. /*
  22. **  Call this with the string to locate to initialize the table
  23. */
  24.  
  25. void init_search(const char *string)
  26. {
  27.       size_t i;
  28.  
  29.       len = strlen(string);
  30.       for (i = 0; i <= UCHAR_MAX; i++)                      /* rdg 10/93 */
  31.             table[i] = len;
  32.       for (i = 0; i < len; i++)
  33.             table[(unsigned char)string[i]] = len - i - 1;
  34.       findme = (char *)string;
  35. }
  36.  
  37. /*
  38. **  Call this with a buffer to search
  39. */
  40.  
  41. char *strsearch(const char *string)
  42. {
  43.       register size_t shift;
  44.       register size_t pos = len - 1;
  45.       char *here;
  46.       size_t limit=strlen(string);
  47.  
  48.       while (pos < limit)
  49.       {
  50.             while( pos < limit &&
  51.                   (shift = table[(unsigned char)string[pos]]) > 0)
  52.             {
  53.                   pos += shift;
  54.             }
  55.             if (0 == shift)
  56.             {
  57.                   if (0 == strncmp(findme,
  58.                         here = (char *)&string[pos-len+1], len))
  59.                   {
  60.                         return(here);
  61.                   }
  62.                   else  pos++;
  63.             }
  64.       }
  65.       return NULL;
  66. }
  67.  
  68. #ifdef TEST
  69.  
  70. #include <stdio.h>
  71.  
  72. void main(void)
  73. {
  74.       char *here;
  75.       char *find_strings[] = {"abb", "you", "not", "it", "dad", "yoo", "hoo",
  76.                               "oo", "oh", "xx", "xx", "x", "x", NULL};
  77.       char *search_strings[] = {"cabbie", "your", "It isn't here",
  78.                                 "But it is here", "hodad", "yoohoo", "yoohoo",
  79.                                 "yoohoo", "yoohoo", "yoohoo", "xx", "x", "."};
  80.       int i;
  81.  
  82.       for (i = 0; find_strings[i]; i++)
  83.       {
  84.             init_search(find_strings[i]);
  85.             here = strsearch(search_strings[i]);
  86.             printf("\"%s\" is%s in \"%s\"", find_strings[i],
  87.                   here ? "" : " not", search_strings[i]);
  88.             if (here)
  89.                   printf(" [\"%s\"]", here);
  90.             putchar('\n');
  91.       }
  92.  
  93. }
  94.  
  95. #endif
  96.