home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume32 / qsearch / part01 / qsearch.c next >
C/C++ Source or Header  |  1992-10-18  |  3KB  |  160 lines
  1.  
  2. /*
  3.  * qsearch.c: fast substring matching in forward and backward direction
  4.  * 9-Oct-1992, Guido Gronek
  5.  */
  6.  
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <limits.h>
  10.  
  11. #include "qsearch.h"
  12.  
  13. #define TEST
  14.  
  15. static size_t Plen;                      /* length of pattern */
  16.  
  17.  
  18. /*
  19.  * generate shift table from pattern string
  20.  * out: address of the initialised shift table
  21.  */
  22. size_t *mktd1(pstr, reverse, td1)
  23. const char *pstr;                   /* pattern string */
  24. int reverse;                        /* reverse order TRUE/FALSE */
  25. shifttab td1;                       /* the caller-supplied shift table */
  26. {
  27.   int c;
  28.   size_t m;
  29.   const char *p;
  30.   size_t * shift;
  31.  
  32.   for (p = pstr; *p; ++p)
  33.     ;
  34.   Plen = m = p - pstr;              /* length of pattern */
  35.  
  36.   for( ++m, shift = td1, c = UCHAR_MAX+1; --c >=0; )
  37.     *shift++ = m;         /* initialize shift table with Plen + 1 */
  38.  
  39.   if (reverse)
  40.     for (shift = td1; p>pstr; )     /* scan pattern right to left */
  41.       shift[*--p] = --m;
  42.   else
  43.     for (shift = td1, p = pstr; *p; ) /* scan pattern left to right */
  44.       shift[*p++] = --m;
  45.  
  46.   return td1;
  47. }
  48.  
  49.  
  50. /* Quicksearch for a pattern in text
  51.  * out: address of the substring in the text or 0 if none
  52.  */
  53. char *qsearch(pstr, text, td1, reverse, tlen)
  54. const char *pstr;                 /* pattern string */
  55. const char *text;                 /* text */
  56. const size_t *td1;                /* shift table ASUMED INITIALISED */
  57. int reverse;                      /* reverse order TRUE/FALSE */
  58. size_t tlen;                      /* text string length if > 0 */
  59. {
  60.   register const char *p, *t, *tx;
  61.   const char *txe;
  62.   size_t m;
  63.  
  64.   if ( pstr==0 || text==0 )
  65.     return 0;
  66.  
  67.   m = Plen;
  68.   if (tlen > 0)               /* length of text string supported */
  69.     txe = text + tlen;
  70.   else
  71.   {
  72.     tx = text;
  73.     while (*tx++)
  74.       ;
  75.     txe = --tx;
  76.   }
  77.   if (reverse)
  78.   {
  79.     tx = txe - m;                  /* rightmost possible match */
  80.     while ( tx >= text )
  81.     {
  82.       p = pstr; t = tx;
  83.       do
  84.       {
  85.         if (*p == 0)               /* pattern scanned completely */
  86.           return (char *)tx;
  87.       } while ( *p++ == *t++ );    /* break if mismatch */
  88.       if ( tx>text )
  89.           tx -= td1[*(tx-1)];      /* shift to previous text location */
  90.       else
  91.         break;
  92.     }
  93.   }
  94.   else
  95.   {
  96.     tx = text;
  97.     while ( tx + m <= txe )
  98.     {
  99.       p = pstr; t = tx;
  100.       do
  101.       {
  102.         if (*p == 0)               /*  pattern scanned completely */
  103.           return (char *)tx;
  104.       } while ( *p++ == *t++ );    /* break if mismatch */
  105.       tx += td1[*(tx+m)];          /* shift to next text location */
  106.     }
  107.   }
  108.   return 0;
  109. }
  110.  
  111.  
  112. #ifdef TEST
  113. #include <stdio.h>
  114. #include <string.h>
  115.  
  116. #define USAGE "usage: qsearch [-r] text pattern\n"
  117.  
  118. char *strsearch(const char *pstr, const char *text, int reverse);
  119.  
  120.  
  121. char *strsearch(text, pstr, reverse)
  122. const char *text;
  123. const char *pstr;
  124. int reverse;
  125. {
  126.   static shifttab shift;
  127.  
  128.   return qsearch( pstr, text, mktd1(pstr,reverse,shift), reverse, 0 );
  129. }
  130.  
  131.  
  132. int main( argc, argv )
  133. int  argc;
  134. char *argv[];
  135. {
  136.   register char *p;
  137.   int reverse;
  138.  
  139.   if ( argc < 3 )
  140.   {
  141.     fprintf(stderr, USAGE);
  142.     exit(1);
  143.   }
  144.   if ( (reverse = strcmp(argv[1],"-r") ==0) !=0 && argc < 4 )
  145.   {
  146.     fprintf(stderr, USAGE);
  147.     exit(1);
  148.   }
  149.  
  150.   p = reverse ? strsearch(argv[2], argv[3], 1) :  
  151.                 strsearch(argv[1], argv[2], 0);
  152.   if ( p == 0 )
  153.     printf("pattern not found\n");
  154.   else
  155.     printf("pattern start: %s\n", p);
  156.   return 0;
  157. }
  158.  
  159. #endif
  160.