1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
/*
** Case-sensitive Boyer-Moore-Horspool pattern match
**
** public domain by Raymond Gardner 7/92
**
** limitation: pattern length + string length must be less than 32767
**
** 10/21/93 rdg Fixed bug found by Jeff Dunlop
*/
#include <limits.h> /* rdg 10/93 */
#include <stddef.h>
#include <string.h>
typedef unsigned char uchar;
#define LARGE 32767
static int patlen;
static int skip[UCHAR_MAX+1]; /* rdg 10/93 */
static int skip2;
static uchar *pat;
void bmh_init(const char *pattern)
{
int i, lastpatchar;
pat = (uchar *)pattern;
patlen = strlen(pattern);
for (i = 0; i <= UCHAR_MAX; ++i) /* rdg 10/93 */
skip[i] = patlen;
for (i = 0; i < patlen; ++i)
skip[pat[i]] = patlen - i - 1;
lastpatchar = pat[patlen - 1];
skip[lastpatchar] = LARGE;
skip2 = patlen; /* Horspool's fixed second shift */
for (i = 0; i < patlen - 1; ++i)
{
if (pat[i] == lastpatchar)
skip2 = patlen - i - 1;
}
}
char *bmh_search(const char *string, const int stringlen)
{
int i, j;
char *s;
i = patlen - 1 - stringlen;
if (i >= 0)
return NULL;
string += stringlen;
for ( ;; )
{
while ( (i += skip[((uchar *)string)[i]]) < 0 )
; /* mighty fast inner loop */
if (i < (LARGE - stringlen))
return NULL;
i -= LARGE;
j = patlen - 1;
s = (char *)string + (i - j);
while (--j >= 0 && s[j] == pat[j])
;
if ( j < 0 ) /* rdg 10/93 */
return s; /* rdg 10/93 */
if ( (i += skip2) >= 0 ) /* rdg 10/93 */
return NULL; /* rdg 10/93 */
}
}
|
