# aho-corasick in Rust: many-pattern search with configurable match semantics

> The aho-corasick crate is a Rust implementation of the Aho-Corasick algorithm for finding many patterns in one pass, with SIMD acceleration in some cases, optional DFA construction, streaming search and replace, and a choice of match semantics that differs from the textbook behaviour. It is dual licensed under MIT and the Unlicense and requires Rust 1.60.0 or newer.

**BurntSushi/aho-corasick** — A fast implementation of Aho-Corasick in Rust.

- Repository: https://github.com/BurntSushi/aho-corasick
- Stars: 1,306 · Forks: 124
- Language: Rust
- License: Unlicense
- Published: 2026-10-19 · Updated: 2026-10-19 · Language: en
- Canonical page: https://hysenlabs.com/projects/burntsushi-aho-corasick

## One pass over the haystack, many patterns at once

The problem this crate solves is the one you hit when you have a list of things to look for in a large body of text. Running a separate search per pattern costs a pass per pattern. Aho-Corasick solves that by building a finite state machine from the pattern set and walking the text once through it, reporting every match as it goes.

The description in the project documentation calls it a fast implementation of Aho-Corasick in Rust, and the features it names are case insensitive matching, overlapping matches, fast searching via SIMD and optional full DFA construction, plus search and replace in streams.

The audience is a Rust developer who has a fixed set of patterns and a lot of text. That is a common shape in practice: a lexer, a linter, a log scanner, a redaction tool, a content filter. The strength of the algorithm is that the automaton is built once, and the per-byte cost during the search does not grow with the number of patterns.

The cost moves to the front. Building the automaton is work proportional to the pattern set, and a program that searches a small amount of text against thousands of patterns will spend most of its time in setup. The crate addresses this with an optional prefilter, which is one of the feature flags described later, but the shape of the trade is inherent to the algorithm rather than an implementation detail.

## The automaton is built once, then searched repeatedly

The API makes the two phases explicit. A builder or constructor takes the patterns and returns an automaton, and the automaton is then used to search:

```rust
use aho_corasick::{AhoCorasick, PatternID};

let patterns = &["apple", "maple", "Snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";

let ac = AhoCorasick::new(patterns).unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
    matches.push((mat.pattern(), mat.start(), mat.end()));
}
```

The `find_iter` method returns an iterator of matches, and each match carries the pattern identifier and the byte offsets of the match. Because it is an iterator, a caller can stop early with `take` or `find`, which matters when the interesting match is near the start of a large file.

The `PatternID` type is what ties a match back to the pattern, and `PatternID::must` is used in the assertions to refer to a pattern by index without a runtime check. The offsets are byte offsets into the haystack, which is the honest thing for a byte-oriented matcher and the thing to remember when the text is UTF-8 and you want character positions.

Searching over a stream of bytes rather than a string is the other half of the design, since the matcher works on byte slices. The crate also provides a `stream_replace_all` method, which is covered below, and the top-level type is built around that byte-oriented view of the problem.

## Match semantics are a choice, and the default is not the intuitive one

This is the part of the crate that has no equivalent in most pattern matching libraries, and it is the part most likely to surprise you.

The textbook description of Aho-Corasick reports all possible matches, including ones that overlap another match. The obvious way to modify that to report only non-overlapping matches does not always behave as expected, because the algorithm reports a match as soon as it sees it. The documentation gives the concrete case: matching the regular expression `Samwise|Sam` against the text `Samwise` yields `Samwise` in a Perl-like or non-POSIX regular expression engine, but the standard modified Aho-Corasick reports `Sam`:

```rust
let ac = AhoCorasick::new(patterns).unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
```

The crate's answer is to make the semantics configurable without adding search time overhead, using a builder:

```rust
use aho_corasick::{AhoCorasick, MatchKind};

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()]);
```

`MatchKind::LeftmostFirst` behaves the way a Perl-like regular expression would. The crate also supports leftmost-longest semantics, which match the POSIX behaviour of a regular expression alternation, and the documentation points at the `MatchKind` type in the API reference for the details.

The practical advice is to decide the semantics before you write assertions against the output, because both variants are correct and they give different answers on overlapping patterns.

## Case insensitivity is a builder option, not a separate matcher

Matching without regard to case is configured on the same builder that takes the match kind. The example in the documentation builds an automaton with ASCII case insensitivity enabled and finds the same three matches in the same haystack as the case-sensitive version:

```rust
let ac = AhoCorasick::builder()
    .ascii_case_insensitive(true)
    .build(patterns)
    .unwrap();
```

Two details are worth noting. The option is named `ascii_case_insensitive`, so it applies to ASCII case folding, which is the cheap case-insensitive comparison, and it is not a general Unicode case folding. The other is that the pattern list in that example is written in lowercase, with the capitalised `Snapple` still matched, which is what a case-insensitive automaton does at build time: the automaton is built with the folding already applied, so the search itself does not pay for it.

Overlapping matches are supported as well, and are the default behaviour of the algorithm, so a caller that needs them does not have to ask for them and a caller that does not need them should reach for a match kind instead.

## Streaming replace avoids loading the file

Search and replace over a stream is the second feature that the crate treats as a first class use case. The documentation's example runs the replacement against a reader and a writer, and notes that in a real program these would be `std::fs::File` values, since all that is required is a pair of `std::io::Read` and `std::io::Write` implementations:

```rust
let patterns = &["fox", "brown", "quick"];
let replace_with = &["sloth", "grey", "slow"];

let rdr = "The quick brown fox.";
let mut wtr = vec![];

let ac = AhoCorasick::new(patterns).unwrap();
ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)
    .expect("stream_replace_all failed");
assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
```

The important property is that the input is never held in memory in full. The matcher consumes chunks from the reader and writes replaced chunks to the writer, so a redaction or substitution pass over a file larger than memory is possible.

The replacement values are indexed by pattern, and the ordering of the output is determined by the match semantics chosen at build time, so the same `MatchKind` decision from the previous section applies here too. A replace pass built with the default semantics on overlapping patterns will produce output that differs from what a regular expression engine would produce for the same patterns.

## Feature flags decide the prefilter, the logging and the DFA

The manifest lists the features, and they tell you a lot about where the tuning knobs are.

The default feature set is `std` plus `perf-literal`. The `std` feature enables the standard library support in the optional `memchr` dependency, and `perf-literal` enables prefilter optimizations that depend on that external crate. A prefilter is the fast path where a literal pattern can be looked for directly rather than through the automaton, which is the mechanism behind the SIMD acceleration the description mentions.

The `logging` feature turns on the `log` crate, and the manifest comment explains its purpose precisely: it is for seeing messages about internal decisions and metrics, such as how the choice of internal Aho-Corasick implementation is used or the heap usage of an automaton. That is a debugging aid for the library itself, not a log of the matches your program found.

There is also a feature providing a trait implementation for `fst::Automaton` for the crate's NFA and DFA types, with a note in the manifest that it is not available while `fst` is not at 1.0, because it would make `fst` a public dependency. The manifest also documents optional full DFA construction as a feature of the crate, which trades memory for search speed.

The practical takeaway is that the default configuration is a sensible starting point, and the flags exist for people who need to see inside the automaton rather than for people who just need to find their patterns.

## Rust 1.60 as a floor, and a permissive licence

The version policy is stated explicitly, and it is a friendly one. The minimum supported `rustc` version is 1.60.0, the manifest sets `rust-version = "1.60.0"` and uses the 2021 edition.

The policy is that the minimum Rust version can be increased in minor version updates. The example in the documentation is that if version 1.0 of a crate requires Rust 1.20.0, then every 1.0.z release will also require it, but 1.y for y greater than zero may require something newer. The stated intent is to be conservative about the minimum supported version.

For a library that other people depend on, that conservatism is the difference between an upgrade that is a version bump and one that breaks a build. It is worth noting that a crate at version 1.1.5 with a 1.60.0 floor is comfortable for most projects, since it is well below what current toolchains require.

The licence is the other thing to check, and it is about as permissive as a licence gets. The crate is dual licensed under MIT or the Unlicense, and the manifest records it as `Unlicense OR MIT`, meaning you can pick either. The repository carries both `LICENSE-MIT` and `UNLICENSE` files alongside a `COPYING` file. Either choice permits use, modification and redistribution, in a closed source product as well as an open one, and the Unlicense in particular places no conditions on redistribution at all.

One more practical note on the repository itself. There is no GitHub release, so versions are tracked on the crate registry, and the last push was on 2026-08-10. The tree also contains a `benchmarks/` directory, a `fuzz/` directory for fuzzing, a `DESIGN.md` document and a separate `aho-corasick-debug` crate, which together tell you the project treats the implementation as something to be measured and attacked as well as used.

## Conclusion

aho-corasick suits a Rust program that needs to find a fixed set of literals fast, whether that is a syntax highlighter, a log filter or a redaction pass, and it is a good fit when the pattern set is known at build time. It is the wrong choice for regular expressions, for patterns that change per record, or for case folding beyond ASCII. Check first the `MatchKind` you want, because the default reports the first match it sees, while leftmost-first follows Perl-like preference order and leftmost-longest follows POSIX order; the difference is visible in the output.

## FAQ

### How do I add the aho-corasick crate to a Rust project?

Run `cargo add aho-corasick`, which adds the dependency to Cargo.toml automatically. The API documentation is on docs.rs, and the crate itself is version 1.1.5 with a minimum supported rustc of 1.60.0.

### What is the difference between the default match kind and LeftmostFirst?

The default reports a match as soon as the automaton sees it, so for the patterns `Samwise` and `Sam` against the text `Samwise` it reports `Sam`. `MatchKind::LeftmostFirst` reports `Samwise` instead, matching how a Perl-like regular expression behaves, and the crate also offers leftmost-longest for POSIX-style semantics.

### Does aho-corasick support case insensitive matching?

Yes. `AhoCorasick::builder().ascii_case_insensitive(true)` enables ASCII case insensitive matching, and the folding is applied when the automaton is built rather than during the search.

### Can aho-corasick replace text in a large file without loading it into memory?

Yes. `stream_replace_all` takes a reader and a writer, so you can pass `std::fs::File` values, and the input is processed as it is read rather than being held in memory in full.

## Sources

- [BurntSushi/aho-corasick on GitHub](https://github.com/BurntSushi/aho-corasick)
- [Issues](https://github.com/BurntSushi/aho-corasick/issues)
- [License: Unlicense](https://github.com/BurntSushi/aho-corasick/blob/master/LICENSE)
- [README](https://github.com/BurntSushi/aho-corasick/blob/master/README.md)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/burntsushi-aho-corasick