ding the leftmost first match In the textbook description of Aho-Corasick, its formulation is typically structured such that it reports all possible matches, even when they overlap with another. In many cases, overlapping matches may not be desired, such as the case of finding all successive non-overlapping matches like you might with a standard regular expression. Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do this doesn't always work in the expected way, since it will report matches as soon as they are seen. For example, consider matching the regex `Samwise|Sam` against the text `Samwise`. Most regex engines (that are Perl-like, or non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick algorithm modified for reporting non-overlapping matches will report `Sam`. A novel contribution of this library is the ability to change the match semantics of Aho-Corasick (without additional search time overhead) such that `Samwise` is reported instead. For example, here's the standard approach: ``` use aho_corasick::AhoCorasick; let patterns = &["Samwise", "Sam"]; let haystack = "Samwise"; let ac = AhoCorasick::new(patterns).unwrap(); let mat = ac.find(haystack).expect("should have a match"); assert_eq!("Sam", &haystack[mat.start()..mat.end()]); ``` And now here's the leftmost-first version, which matches how a Perl-like regex will work: ``` use aho_corasick::{AhoCorasick, MatchKind}; let patterns = &["Samwise", "Sam"]; let haystack = "Samwise"; let ac = AhoCorasick::builder() .match_kind(MatchKind::LeftmostFirst) .build(patterns) .unwrap(); let mat = ac.find(haystack).expect("should have a match"); assert_eq!("Samwise", &haystack[mat.start()..mat.end()]); ``` In addition to leftmost-first semantics, this library also supports leftmost-longest semantics, which match the POSIX behavior of a regular expression alternation. See [`MatchKind`] for more details. # Prefilters While an Aho-Corasick automaton can perform admirably when compared to more naive solutions, it is generally slower than more specialized algorithms that are accelerated using vector instructions such as SIMD. For that reason, this library will internally use a "prefilter" to attempt to accelerate searches when possible. Currently, this library has several different algorithms it might use depending on the patterns provided. Once the number of patterns gets too big, prefilters are no longer used. While a prefilter is generally good to have on by default since it works well in the common case, it can lead to less predictable or even sub-optimal performance in some cases. For that reason, prefilters can be explicitly disabled via [`AhoCorasickBuilder::prefilter`]. # Lower level APIs This crate also provides several sub-modules that collectively expose many of the implementation details of the main [`AhoCorasick`] type. Most users of this library can completely ignore the submodules and their contents, but if you needed finer grained control, some parts of them may be useful to you. Here is a brief overview of each and why you might want to use them: * The [`packed`] sub-module contains a lower level API for using fast vectorized routines for finding a small number of patterns in a haystack. You might want to use this API when you want to completely side-step using Aho-Corasick automata. Otherwise, the fast vectorized routines are used automatically as prefilters for `AhoCorasick` searches whenever possible. * The [`automaton`] sub-module provides a lower level finite state machine interface that the various Aho-Corasick implementations in this crate implement. This sub-module's main contribution is the [`Automaton`](automaton::Automaton) trait, which permits manually walking the state transitions of an Aho-Corasick automaton. * The [`dfa`] and [`nfa`] sub-modules provide DFA and NFA implementations of the aforementioned `Automaton` trait. The main reason one might want to use these sub-modules is to get access to a type that implements the `Automaton` trait. (The top-level `AhoCorasick` type does not implement the `Automaton` trait.) As mentioned above, if you aren't sure whether you need these sub-modules, you should be able to safely ignore them and just focus on the [`AhoCorasick`] type. # Crate features This crate exposes a few features for controlling dependency usage and whether this crate can be used without the standard library. * **std** - Enables support for the standard library. This feature is enabled by default. When disabled, only `core` and `alloc` are used. At an API level, enabling `std` enables `std::error::Error` trait impls for the various error types, and higher level stream search routines such as [`AhoCorasick::try_stream_find_iter`]. But the `std` feature is also required to enable vectorized prefilters. Prefilters can greatly accelerate searches, but generally only apply when the number of patterns is small (less than ~100). * **perf-literal** - Enables support for literal prefilters that use vectorized routines from external crates. This feature is enabled by default. If you're only using Aho-Corasick for large numbers of patterns or otherwise can abide lower throughput when searching with a small number of patterns, then it is reasonable to disable this feature. * **logging** - Enables a dependency on the `log` crate and emits messages to aide in diagnostics. This feature is disabled by default.