aho-corasick

aho-corasick builds a finite state machine from a set of patterns and then searches text for all occurrences of any of them in a single linear-time pass, rather than running one search per pattern. It’s the multi-pattern search engine underneath widely used Rust tools including ripgrep and the regex crate, and it offers case-insensitive matching, overlapping matches, leftmost-first/leftmost-longest match semantics, and both non-contiguous and contiguous NFA representations as well as an optional full DFA for maximum search throughput at the cost of build time and memory.

Where the input allows it, aho-corasick uses SIMD-accelerated prefilters (via the memchr crate’s perf-literal feature) to skip ahead through text that can’t possibly start a match, and it supports streaming search-and-replace so patterns can be matched and substituted incrementally without loading an entire haystack into memory.

What You Get

• An AhoCorasick type built from a pattern list via AhoCorasick::new, returning Match results with pattern ID and byte offsets from find_iter
• AhoCorasickBuilder for configuring case-insensitivity, overlapping matches, leftmost-first vs. leftmost-longest semantics, and which internal automaton kind to use
• Multiple automaton backends: a noncontiguous NFA (fast to build, more memory), a contiguous NFA, and a full DFA (fastest search, slowest build/most memory)
• SIMD-accelerated prefilters via the optional perf-literal feature (enabled by default) built on the memchr crate
• Streaming search-and-replace support, plus an optional fst::Automaton trait implementation for searching finite-state transducers
• no_std-compatible core with an alloc-only mode alongside the full std feature

Common Use Cases

• Multi-keyword text search and content filtering, e.g. scanning documents for any of thousands of banned words or trademarks in one pass
• Underlying engine for line-oriented search tools (this crate is the literal engine inside ripgrep for certain pattern-set searches)
• Log or stream processing that needs to detect and replace many fixed substrings without buffering the entire input
• Bioinformatics or text-processing pipelines needing to locate all occurrences of a large, fixed dictionary of substrings efficiently

Under The Hood

Architecture: The crate’s core lives in src/ahocorasick.rs (the public AhoCorasick façade and builder), src/nfa/ (noncontiguous and contiguous NFA construction and search), src/dfa.rs (the optional fully-expanded DFA), src/automaton.rs (a shared trait unifying search behavior across all three representations), and src/packed/ (SIMD-accelerated packed-string search used as a prefilter for small pattern sets). src/transducer.rs bridges to the fst crate’s automaton trait for searching finite-state transducers. This layered design lets AhoCorasick pick the cheapest-to-build representation that still meets a caller’s throughput needs, switching automaton kind via AhoCorasickBuilder without changing the public search API.

Tech Stack: Pure Rust, edition 2021, MSRV 1.60, with an optional memchr dependency (perf-literal feature, default-on) providing SIMD prefiltering, an optional log dependency for internal decision tracing, and an experimental fst integration gated behind a feature flag specifically to avoid making fst a public dependency before its 1.0 release. The crate builds in both std and alloc-only/no_std configurations.

Code Quality: A dedicated aho-corasick-debug crate and benchmarks/ directory support performance regression testing, and DESIGN.md documents the algorithmic tradeoffs between the NFA and DFA representations in depth — unusually thorough for a crate of this size. src/tests.rs (1,664 lines) drives correctness testing across match semantics (leftmost-first, leftmost-longest, overlapping) and automaton kinds, and a fuzz/ directory backs the parser/automaton construction with fuzz testing. As a BurntSushi crate sharing infrastructure with regex and ripgrep, it inherits that ecosystem’s high bar for correctness and benchmarking discipline.

API Design: The default path (AhoCorasick::new(patterns) + find_iter) covers the common case in two lines, while AhoCorasickBuilder exposes the deeper configuration (match kind, automaton kind, case sensitivity) for callers who need to tune build-time-vs-search-time tradeoffs explicitly. Match results expose .pattern(), .start(), .end() directly rather than requiring callers to reconstruct positions, and the crate’s docs.rs documentation includes runnable examples for each major mode (basic search, case-insensitive, overlapping, replace-all), lowering the barrier to using the more advanced features correctly.