|
<![CDATA[
char *search( k, pat, text, n ) /*** at most k errors ***/
int k, n;
char *pat, *text;
{ int T[MAXPATLEN+1];
int i, j, m, tj, tj1;
m = strlen( pat );
if( m <= k ) return( text + n );
T[0] = 0; /*** initial values ***/
for( j=1; j<=m; j++ ) T[j] = j;
for( i=1; i<=n; i++ ) { /*** search ***/
tj1 = 0;
for( j=1; j<=m; j++ ) {
tj = T[j];
if( text[n-i] != pat[m-j] ) tj1++;
if( tj+1 < tj1 ) tj1 = tj+1;
if( T[j-1]+1 < tj1 ) tj1 = T[j-1]+1;
T[j] = tj1;
tj1 = tj;
}
if( T[m] <= k ) return( text+n-i );
}
return( NULL );
}
]]> |
![[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 (718b.srch.c) 