src/filter-env/bmh_search.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* raided from http://www.dcc.uchile.cl/~rbaeza/handbook/algs/7/713b.srch.c.html
aparently distributed by Addison-Wesley Publishing Co. Inc, http://aw.com/
*/

#include <string.h>
#define MAXCHAR 256

const char *bmh_search( const char *pat, const char *text, int n )
{ int i, j, k, m, skip[MAXCHAR];

    m = strlen(pat);
    if( m==0 ) return( text );
    for( k=0; k<MAXCHAR; k++ ) skip[k] = m;
    for( k=0; k<m-1; k++ ) skip[pat[k]] = m-k-1;

    for( k=m-1; k < n; k += skip[text[k] & (MAXCHAR-1)] ) {
	for( j=m-1, i=k; j>=0 && text[i] == pat[j]; j-- ) i--;
	if( j == (-1) ) return( text+i+1 );
    }
    return( NULL );
}