|
<![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) 