Автор: Thierry Lecroq
Перевод: Кантор И.

Вариант алгоритма быстрого поиска, просматривающий символы образца от соответствующего наибольшему сдвигу к наименьшему.

Реализация на Си

   typedef struct pattern_scan_order {
      int loc;
      char c;
   } PAT;
   
   int MinShift[XSIZE];
   
   /* Computation of the MinShift table values. */
   void COMPUTE_MINSHIFT(char *x, int m)
   {
    int i, j;
   
    for (i=0; i < m; i++) {
       for (j=i-1; j >= 0; j--)
           if (x[j] == x[i]) break;
       MinShift[i]=i-j;
    }
   }
   
   /* Construct an ordered pattern from a string. */
   void ORDER_PATTERN(char *x, int m, int (*pcmp)(), PAT *pattern)
   {
    int i;
   
    for (i=0; i <= m; i++) {
       pattern[i].loc=i;
       pattern[i].c=x[i];
    }
    qsort(pattern, m, sizeof(PAT), pcmp);
   }
   
   
   /* Maximal Shift pattern comparison function. */
   int MAXSHIFT_PCMP(PAT *pat1, PAT *pat2)
   {
    int dsh;
   
    dsh=MinShift[pat2->loc]-MinShift[pat1->loc];
    return(dsh ? dsh : (pat2->loc-pat1->loc));
   }
   
   
   /* Constructs the delta 1 shift table from a pattern string. */
   void BUILD_TD1(char *x, int m, int *td1)
   {
    int a, j;
   
    for (a=0; a < ASIZE; a++) td1[a]=m+1;
    for (j=0; j < m; j++) td1[x[j]]=m-j;
   }
   
   
   /* Find the next leftward matching shift for the first ploc pattern */
   /*  elements after a current shift or lshift.                       */
   int MATCHSHIFT(char *x, int m, int ploc, int lshift, PAT *pattern)
   {
    int i, j;
   
    for (; lshift < m; lshift++) {
       i=ploc;
       while (--i >= 0) {
          if ((j=(pattern[i].loc-lshift)) < 0) continue;
          if (pattern[i].c != x[j]) break;
       }
       if (i < 0) break;
    }
    return(lshift);
   }
   
   
   /* Constructs the delta2 shift table from an ordered string. */
   void BUILD_TD2(char *x, int m, int *td2, PAT *pattern)
   {
    int lshift, i, ploc;
   
    td2[0]=lshift=1;
    for (ploc=1; ploc <= m; ploc++) {
       lshift=MATCHSHIFT(x, m, ploc, lshift, pattern);
       td2[ploc]=lshift;
    }
    for (ploc=0; ploc <= m; ploc++) {
       lshift=td2[ploc];
       while (lshift < m) {
          i=pattern[ploc].loc-lshift;
          if (i < 0 || pattern[ploc].c != x[i]) break;
          lshift++;
          lshift=MATCHSHIFT(x, m, ploc, lshift, pattern);
       }
       td2[ploc]=lshift;
    }
   }
   
   /* Maximal Shift string matching algorithm. */
   void MS(char *y, char *x, int n, int m)
   {
    int i, j, td2[XSIZE], td1[ASIZE];
    PAT pattern[XSIZE];
   
    /* Preprocessing */
    COMPUTE_MINSHIFT(x ,m);
    ORDER_PATTERN(x, m, MAXSHIFT_PCMP, pattern);
    BUILD_TD1(x, m, td1);
    BUILD_TD2(x, m, td2, pattern);
   
    /* Searching */
    i=0;
    while (i <= n-m) {
       j=0;
       while (j < m && y[i+pattern[j].loc] == pattern[j].c) j++;
       if (j >= m) OUTPUT(i);
       i+=MAX(td1[y[i+m]], td2[j]);
    }
   }