2 * Knuth-Morris-Pratt's Substring Search for N given strings
4 * (c) 1999--2005, Robert Spalek <robert@ucw.cz>
5 * (c) 2006, Pavel Charvat <pchar@ucw.cz>
7 * (In fact, the algorithm is usually referred to as Aho-McCorasick,
8 * but that's just an extension of KMP to multiple strings.)
12 * This is not a normal header file, it's a generator of KMP algorithm.
13 * Each time you include it with parameters set in the corresponding
14 * preprocessor macros, it generates KMP structures and functions
15 * with the parameters given. Macros marked with [*] are mandatory.
17 * [*] KMPS_PREFIX(x) macro to add a name prefix (used on all global names
18 * defined by the KMP search generator)
19 * [*] KMPS_KMP_PREFIX(x) prefix used for lib/kmp.h;
20 * more variants of kmp-search can be used for single lib/kmp.h
22 * KMPS_SOURCE user-defined search input (together with KMPS_GET_CHAR);
23 * if unset, the one from lib/kmp.h is used
24 * KMPS_GET_CHAR(ctx,src,s)
26 * KMPS_ADD_CONTROLS add control characters at both ends of the input string
27 * KMPS_MERGE_CONTROLS merge adjacent control characters to a single one
29 * KMPS_EXTRA_ARGS extra arguments to the search routine
30 * KMPS_EXTRA_VAR extra user-defined structure in search structures
31 * KMPS_INIT(ctx,src,s)
32 * KMPS_EXIT(ctx,src,s)
33 * KMPS_FOUND(ctx,src,s)
34 * KMPS_FOUND_CHAIN(ctx,src,s)
35 * KMPS_STEP(ctx,src,s)
41 #define P(x) KMPS_PREFIX(x)
42 #define KP(x) KMPS_KMP_PREFIX(x)
45 typedef KMPS_SOURCE P(search_source_t);
47 typedef KP(source_t) P(search_source_t);
51 #define KMPS_GET_CHAR(ctx,src,s) ({ KP(get_char)(ctx, &src, &s.c); })
55 struct KP(state) *s; /* current state */
56 struct KP(state) *out; /* output state */
57 # ifdef KMPS_WANT_BEST
58 struct KP(state) *best; /* longest match */
60 KP(char_t) c; /* last character */
61 # ifdef KMPS_EXTRA_VAR
62 KMPS_EXTRA_VAR v; /* user-defined */
64 # ifdef KMPS_ADD_CONTROLS
74 P(search) (struct KP(context) *ctx, P(search_source_t) src
75 # ifdef KMPS_EXTRA_ARGS
82 # ifdef KMPS_WANT_BEST
85 # ifdef KMPS_ADD_CONTROLS
86 s.c = KP(control_char)();
92 { KMPS_INIT(ctx, src, s); }
94 # ifndef KMPS_ADD_CONTROLS
99 for (struct KP(state) *t = s.s; t && !(s.s = KP(hash_find)(&ctx->hash, t, s.c)); t = t->back);
100 s.s = s.s ? : &ctx->null;
103 { KMPS_STEP(ctx, src, s); }
106 # if defined(KMPS_FOUND) || defined(KMPS_FOUND_CHAIN) || defined(KMPS_WANT_BEST)
107 s.out = s.s->len ? s.s : s.s->next;
110 # ifdef KMPS_WANT_BEST
111 if (s.out->len > s.best->len)
114 #ifdef KMPS_FOUND_CHAIN
115 { KMPS_FOUND_CHAIN(ctx, src, s); }
119 { KMPS_FOUND(ctx, src, s); }
120 while (s.out = s.out->next);
125 # ifdef KMPS_ADD_CONTROLS
130 # ifndef KMPS_ADD_CONTROLS
133 # ifdef KMPS_MERGE_CONTROLS
134 KP(char_t) last_c = s.c;
139 if (!KMPS_GET_CHAR(ctx, src, s))
141 # ifdef KMPS_ADD_CONTROLS
142 if (s.c != KP(control_char)())
144 s.c = KP(control_char)();
153 # ifdef KMPS_MERGE_CONTROLS
154 || (last_c == KP(control_char)() && s.c == KP(control_char)())
160 { KMPS_EXIT(ctx, src, s); }
166 #undef KMPS_KMP_PREFIX
169 #undef KMPS_ADD_CONTROLS
170 #undef KMPS_MERGE_CONTROLS
171 #undef KMPS_EXTRA_ARGS
172 #undef KMPS_EXTRA_VAR
176 #undef KMPS_FOUND_CHAIN
179 #undef KMPS_WANT_BEST