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

Этот вариант алгоритма быстрого поиска просматривает символы образца от наименее к наиболее частому. Таким образом мы сможем получать больше несовпадений.

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

   typedef struct pattern_scan_order {
      int loc;
      char c;
   } PAT;
   
   int Freq[ASIZE];
   
   /* 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);
   }
   
   /* Optimal Mismatch pattern comparison function. */
   int OPTIMAL_PCMP(PAT *pat1, PAT *pat2)
   {
    float fx;
   
    fx=Freq[pat1->loc]-Freq[pat2->loc];
    return(fx ? (fx > 0 ? 1 : -1) : (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 delta 2 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;
    }
   }
   
   /* Optimal Mismatch string matching algorithm. */
   void OM(char *y, char *x, int n, int m)
   {
    int i, j, td2[XSIZE], td1[ASIZE];
    PAT pattern[XSIZE];
   
    /* Preprocessing */
    ORDER_PATTERN(x, m, OPTIMAL_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]);
    }
   }