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


Shift-or text searching


char *search( pat, text ) char *pat, *text; { int B, bits, i, m, mask[MAXCHAR]; if( pat[0]==EOS ) return( text ); B = 1; for( m=0; m<MAXCHAR; m++ ) mask[m] = ~0; for( m=0; B != 0 && pat[m] != EOS; m++ ) { mask[pat[m]] &= ~B; B <<= 1; } B = 1<<(m-1); for( bits=~0; *text != EOS; text++ ) { bits = bits<<1 | mask[*text & (MAXCHAR-1)]; if( (bits&B) == 0 ) { for( i=0; pat[m+i] != EOS && pat[m+i]==text[i+1]; i++ ); if( pat[m+i]==EOS ) return( text-m+1 ); } } return( NULL ); }

C source (717.srch.c)



© Addison-Wesley Publishing Co. Inc.