2.11BSD#431 - /usr/src/new/bm/MakeSkip.c

   1: #include "bm.h"
   2: extern char *malloc();
   3: 
   4: MakeSkip(Pattern,Skip1,Skip2,PatLen)
   5: char Pattern[];
   6: int Skip1[], Skip2[];
   7: int PatLen;
   8: /* generate the skip tables for Boyer-Moore string search algorithm.
   9: * Skip1 is the skip depending on the character which failed to match
  10: * the pattern, and Skip2 is the skip depending on how far we got into
  11: * the pattern. Pattern is the search pattern and PatLen is strlen(Pattern) */
  12: {
  13:     int *BackTrack; /* backtracking table for t when building skip2 */
  14:     int c; /* general purpose constant */
  15:     int j,k,t,tp; /* indices into Skip's and BackTrack */
  16: 
  17:     if (!(BackTrack = (int *) malloc(PatLen * (sizeof (int))))){
  18:         fprintf("bm: can't allocate space\n");
  19:         exit(2);
  20:     } /* if */
  21:     for (c=0; c<=MAXCHAR; ++c)
  22:         Skip1[c] = PatLen;
  23:     for (k=0;k<PatLen;k++) {
  24:         Skip1[Pattern[k]] = PatLen - k - 1;
  25:         Skip2[k] = 2 * PatLen - k - 1;
  26:     } /* for */
  27:     for (j=PatLen - 1,t=PatLen;j >= 0; --j,--t) {
  28:         BackTrack[j] = t;
  29:         while (t<PatLen && Pattern[j] != Pattern[t]) {
  30:             Skip2[t] = min(Skip2[t], PatLen - j - 1);
  31:             t = BackTrack[t];
  32:         } /* while */
  33:     } /* for */
  34:     for (k=0;k<=t;++k)
  35:         Skip2[k] = min(Skip2[k],PatLen+t-k);
  36:     tp=BackTrack[t];
  37:     while(tp<PatLen) {
  38:         while(t<PatLen) {
  39:             Skip2[t] = min(Skip2[t],tp-t+PatLen);
  40:             ++t;
  41:         } /* while */
  42:         tp = BackTrack[tp];
  43:     } /* while */
  44:     cfree(BackTrack);
  45: } /* MakeSkip */

Defined functions