Aho–Corasick Match Kinds in Rust: Standard, Leftmost-First, and Leftmost-Longest

Article · Through the layers

A multi-pattern search is not fully specified by its patterns. I must also decide which result wins when several matches overlap.

This is easy to miss because simple examples contain only one possible match. Real dictionaries contain prefixes: app, append, and appendage. Security rules overlap. Token names share beginnings. At that point, “find the match” is not one operation.

Rust's aho-corasick crate offers three match kinds: Standard, LeftmostFirst, and LeftmostLongest. None is universally correct. Each answers a different question.

One example exposes all three

Use these patterns in this exact order:

0: b
1: abc
2: abcd

The haystack is abcd.

Standard semantics reports b at 1..2. The automaton sees that complete match before it reaches the end of abc or abcd.

Leftmost-first reports abc at 0..3. It prefers the earliest starting position. Among patterns beginning there, the pattern appearing first in the pattern list wins. Here abc comes before abcd.

Leftmost-longest reports abcd at 0..4. It prefers the earliest starting position and then the longest match at that position.

This program keeps the difference executable:

use aho_corasick::{AhoCorasick, MatchKind};

fn selected(kind: MatchKind) -> (usize, usize, usize) {
    let matcher = AhoCorasick::builder()
        .match_kind(kind)
        .build(["b", "abc", "abcd"])
        .unwrap();
    let found = matcher.find("abcd").unwrap();
    (found.pattern().as_usize(), found.start(), found.end())
}

fn main() {
    assert_eq!((0, 1, 2), selected(MatchKind::Standard));
    assert_eq!((1, 0, 3), selected(MatchKind::LeftmostFirst));
    assert_eq!((2, 0, 4), selected(MatchKind::LeftmostLongest));
}

These results follow the crate's official matching examples.

Standard means detection order

Standard match semantics is closest to the textbook Aho–Corasick behavior. A match can be reported as soon as the automaton detects it. “First” here is not necessarily the match with the smallest starting offset.

That sentence matters. In the example, b begins later than abc, but it finishes earlier and is detected first.

I choose standard semantics when I need overlapping matches, streaming search with the crate's stream API, or the complete set of detected patterns. It is also a good default when the application treats every detected pattern independently.

Standard does not mean “best natural-language result.” A user highlighting dictionary terms may expect the longest word, while standard semantics can choose a shorter pattern detected earlier.

Leftmost-first makes pattern order part of behavior

Leftmost-first first selects the match beginning furthest to the left. If several patterns begin there, the one inserted earliest wins.

This makes pattern order a priority system. With patterns app then apple, apple can never win at a position beginning with apple, because app has higher order priority. Reverse the pattern order and the result changes.

I use this only when priority is intentional and tested. Configuration coming from a database or hash-based collection must have a stable order. Otherwise a refactor can silently change matching behavior without changing any pattern text.

This mode can be useful for lexer-like rules where explicit precedence is part of the language. I document that precedence next to the pattern definitions, not only in the matcher construction.

Leftmost-longest chooses maximal coverage

Leftmost-longest selects the earliest starting position and then the longest pattern beginning there. Pattern order is not the tie-breaker for different lengths.

This is often closer to dictionary extraction, redaction, or highlighting where New York should win over New at the same position. But “longest” still does not mean globally optimal coverage. It is a local rule anchored at the next leftmost start.

The scanner may need to continue after seeing a shorter match because a longer one could still complete. That delayed decision is one reason match semantics influence streaming design and buffering.

Overlapping is a separate choice

Normal find_iter calls report non-overlapping matches. find_overlapping_iter reports every possible match at every position, but the crate supports this only with standard semantics.

That restriction is coherent: leftmost modes exist to choose among competing matches, while an overlapping search asks to keep all of them. The MatchKind documentation states that overlapping and stream searches require standard semantics.

I use fallible try_ search methods when matcher configuration is not a fixed program invariant. The infallible methods may panic for an unsupported combination such as a leftmost automaton with a stream search.

Choose from the product rule

I do not start with the fastest enum. I write examples of disputed input and expected output:

Then I test prefixes, duplicate patterns, adjacent matches, empty patterns if allowed, and patterns whose end positions differ. These cases reveal assumptions hidden by friendly examples.

Semantics come before optimization

Changing match kind can change both the output and the automaton construction. A faster benchmark is meaningless if it selects a different match. I first freeze the expected sequence of (pattern_id, start, end), and only then compare representations or prefilters.

This lesson applies beyond Aho–Corasick. Database conflict resolution, router precedence, firewall rules, parsers, and schedulers all need a tie-breaking contract. If the contract is implicit, implementation order becomes accidental product behavior.

For how these choices affect retained bytes, see Why Aho–Corasick Streaming Still Needs a Buffer. The wider streaming and zero-copy model is in Zero-Copy Does Not Mean Zero Memory Access.