|
<![CDATA[
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];
}
}
]]> |
![[Home]](../../images/home_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (713.preproc.c) 