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


String matching with k errors


int searchword( pat, cd ) char *pat; ControlDict cd; { int i, j, m, hi, lo; extern int hits; lo = -1; hi = K; for( m=hi; m-lo > 1; ) { j = (m+lo) / 2; for( i=0; pat[i] != EOS && cd[j][i] != EOS && cd[j][i] == pat[i]; ); if( pat[i] != EOS && cd[j][i] < pat[i] ) lo = j; else m = j; } for( m=lo; hi-m > 1; ) { j = (hi+m) / 2; for( i=0; pat[i] != EOS && cd[j][i] != EOS && cd[j][i] == pat[i]; ); if( pat[i] != EOS && cd[j][i] > pat[i] ) hi = j; else m = j; } hits = hi-lo-1; return( hits > 0 ? lo+1 : -1 ); }

C source (721.srchw.c)



© Addison-Wesley Publishing Co. Inc.