Expand description
An implementation of the Two-Way substring search algorithm.
Finder can be built for forward searches, while FinderRev can be built
for reverse searches.
Two-Way makes for a nice general purpose substring search algorithm because of
its time and space complexity properties. It also performs well in practice.
Namely, with m = len(needle) and n = len(haystack), Two-Way takes O(m)
time to create a finder, O(1) space and O(n) search time. In other words,
the preprocessing step is quick, doesn’t require any heap memory and the worst
case search time is guaranteed to be linear in the haystack regardless of the
size of the needle.
While vector algorithms will usually beat Two-Way handedly, vector algorithms also usually have pathological or edge cases that are better handled by Two-Way. Moreover, not all targets support vector algorithms or implementations for them simply may not exist yet.
Two-Way can be found in the memmem implementations in at least GNU libc and
musl.
Structs§
- A forward substring searcher that uses the Two-Way algorithm.
- A reverse substring searcher that uses the Two-Way algorithm.