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