[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


Boyer-Moore preprocessing


void preprocpat( pat, skip, d ) char *pat; int skip[], d[]; { int j, k, m, t, t1, q, q1; int f[MAXPATLEN]; /*** auxiliary table ***/ m = strlen( pat ); for( k=0; k<MAXCHAR; k++ ) skip[k] = m; for( k=1; k<=m; k++ ) { d[k-1] = (m << 1) - k; skip[pat[k-1]] = m-k; } t = m + 1; for( j=m; j > 0; j-- ) { f[j-1] = t; while( t <= m && pat[j-1] != pat[t-1] ) { d[t-1] = min( d[t-1], m-j ); t = f[t-1]; } t--; } q = t; t = m + 1 - q; q1 = 1; t1 = 0; for( j=1; j<=t; j++ ) { f[j-1] = t1; while( t1 >= 1 && pat[j-1] != pat[t1-1] ) t1 = f[t1-1]; t1++; } while( q < m ) { for( k=q1; k<=q; k++ ) d[k-1] = min( d[k-1], m+q-k ); q1 = q + 1; q = q + t - f[t-1]; t = f[t-1]; } }

C source (713.preproc.c)



© Addison-Wesley Publishing Co. Inc.