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