home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / SRC / boyerm.c next >
C/C++ Source or Header  |  2009-11-06  |  3KB  |  128 lines
  1. /* boyerm - find lines containing given constant string       */
  2. /* A. Kotanski, 1989                                          */
  3. /* For explanation of the method see the following articles : */
  4. /* R.S.Boyer, J.S. Moore, "A fast string search algorithm"    */
  5. /*                        Comm. ACM 20, 762-772 (1977)        */
  6. /* D.E.Knuth, J.H.Morris and V.B.Pratt                        */
  7. /*                        "Fast pattern matching in strings"  */
  8. /*                        SIAM J. Computing, 6, 323-350 (1977)*/
  9.  
  10. #include <stdio.h>
  11.  
  12. #define large 0x6000
  13. #ifdef OSK
  14. #define max(a,b) ((a)>(b)?(a):(b))
  15. #define min(a,b) ((a)>(b)?(b):(a))
  16. #endif
  17.  
  18. direct int except = 0, number = 0, ppos = 1;
  19. direct int patlen, stringlen;
  20. int delta0[128], delta2[80];
  21. direct int c, argsused = 0;
  22. char string[256], pat[80], f[80];
  23. extern char *optarg;
  24. extern int optind, opterr;
  25.  
  26. main(argc, argv)  /* find pattern from first argument */
  27. int argc;
  28. char *argv[];
  29. {
  30.    int lineno = 0, match;
  31.    register int i, t;
  32.  
  33.    while ((c = getopt(argc, argv, "nj:x")) != EOF ) {
  34.       switch (c) {
  35.       case 'n': 
  36.          number =1;
  37.          argsused++;
  38.          break;
  39.       case 'j': 
  40.          ppos = atoi(optarg);
  41.          argsused++;
  42.          break;
  43.       case 'x': 
  44.          except = 1;
  45.          argsused++;
  46.          break;
  47.       case '?': 
  48.          fputs("Usage: boyerm \"pattern\" <file\n", stderr);
  49.          fputs("Optional arguments:\n", stderr);
  50.          fputs("  -n         print line numbers\n", stderr);
  51.          fputs("  -j<number> start comparing at column <number>\n", stderr);
  52.          fputs("  -x         print lines that do not match\n\n", stderr);
  53.          exit(0);
  54.       }
  55.    }
  56.    if ( argc - argsused == 1 ) {
  57.       setbuf(stderr, 0);
  58.       fputs("boyerm: pattern = ", stderr);
  59.       readln(2, pat, 80);
  60.       pat[strlen(pat) - 1] = '\0';
  61.    } 
  62.    else
  63.       strcpy(pat, argv[optind]);
  64.  
  65.    patlen = strlen(pat);
  66.  
  67.    for ( i = 0; i < 128; i++ )
  68.       delta0[i] = patlen;
  69.    for ( i = 0; i < patlen; i++ )
  70.       delta0[pat[i]] = patlen - i - 1;
  71.  
  72.    delta0[pat[patlen - 1]] = large;
  73.  
  74.    for ( i = 0; i < patlen; i++)
  75.       delta2[i] = patlen + patlen - i - 1;
  76.  
  77.    i = patlen - 1;
  78.    t = patlen;
  79.    while ( i >= 0 ) {
  80.       f[i] = t;
  81.       while ( ( t < patlen ) && ( pat[i] != pat[t] ) ) {
  82.          delta2[t] = min(delta2[t], patlen-i-1);
  83.          t = f[t];
  84.       }
  85.       t--;
  86.       i--;
  87.    }
  88.    for ( i = 0; i <= t; i++)
  89.       delta2[i] = min(delta2[i], patlen + t - i);
  90.  
  91.    while( gets(string) ) {
  92.       lineno++;
  93.       stringlen = strlen(string);
  94.       match = boyer();
  95.       if ( (match && !except) || (!match && except) ) {
  96.          if (number)
  97.              printf("%d: ", lineno);
  98.          puts(string);
  99.       }
  100.    }
  101. }
  102.  
  103. int boyer()
  104. {
  105.    register int i, j;
  106.  
  107.    if ( (i = patlen + ppos - 2) >= stringlen )
  108.        return 0;
  109.    for ( ; ; ) {
  110.       while ( (i += delta0[string[i]]) < stringlen )
  111.           ;
  112.       if ( i < large )
  113.           return 0;
  114.       i -= large + 1;
  115.       if ( (j = patlen - 2) < 0 )
  116.           return i + 2;
  117.       while ( string[i] == pat[j] ) {
  118.          i--;
  119.          if ( --j < 0 )
  120.              return i + 2;
  121.       }
  122.       if ( string[i] == pat[patlen-1] )
  123.           i += delta2[j];
  124.       else
  125.          i += max(delta0[string[i]], delta2[j]);
  126.    }  
  127. }
  128.