Этот вариант алгоритма быстрого поиска просматривает символы образца от наименее к наиболее частому. Таким образом мы сможем получать больше несовпадений. Реализация на Си 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]); } }  8  Комментарии к статье  8 8  Обсудить в чате