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 ); } |