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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
/*
** A Pratt-Boyer-Moore string search, written by Jerry Coffin
** sometime or other in 1991. Removed from original program, and
** (incorrectly) rewritten for separate, generic use in early 1992.
** Corrected with help from Thad Smith, late March and early
** April 1992...hopefully it's correct this time. Revised by Bob Stout.
**
** This is hereby placed in the Public Domain by its author.
**
** 10/21/93 rdg Fixed bug found by Jeff Dunlop
*/
#include <stddef.h>
#include <string.h>
#include <limits.h>
static size_t table[UCHAR_MAX];
static size_t len;
static char *findme;
/*
** Call this with the string to locate to initialize the table
*/
void init_search(const char *string)
{
size_t i;
len = strlen(string);
for (i = 0; i <= UCHAR_MAX; i++) /* rdg 10/93 */
table[i] = len;
for (i = 0; i < len; i++)
table[(unsigned char)string[i]] = len - i - 1;
findme = (char *)string;
}
/*
** Call this with a buffer to search
*/
char *strsearch(const char *string)
{
register size_t shift;
register size_t pos = len - 1;
char *here;
size_t limit=strlen(string);
while (pos < limit)
{
while( pos < limit &&
(shift = table[(unsigned char)string[pos]]) > 0)
{
pos += shift;
}
if (0 == shift)
{
if (0 == strncmp(findme,
here = (char *)&string[pos-len+1], len))
{
return(here);
}
else pos++;
}
}
return NULL;
}
#ifdef TEST
#include <stdio.h>
void main(void)
{
char *here;
char *find_strings[] = {"abb", "you", "not", "it", "dad", "yoo", "hoo",
"oo", "oh", "xx", "xx", "x", "x", NULL};
char *search_strings[] = {"cabbie", "your", "It isn't here",
"But it is here", "hodad", "yoohoo", "yoohoo",
"yoohoo", "yoohoo", "yoohoo", "xx", "x", "."};
int i;
for (i = 0; find_strings[i]; i++)
{
init_search(find_strings[i]);
here = strsearch(search_strings[i]);
printf("\"%s\" is%s in \"%s\"", find_strings[i],
here ? "" : " not", search_strings[i]);
if (here)
printf(" [\"%s\"]", here);
putchar('\n');
}
}
#endif
|
