Aho-Corasick multi-pattern matching

Deep dive

How it works

In: pattern byte strings, then text bytes (in chunks) · Out: (pattern, start, end) for every occurrence, in order of end offset · State: current automaton state (one u32) plus bytes consumed so far · Cost: build O(total pattern bytes), scan O(n + z), one table load per byte

1. Trie: insert every pattern; the node reached by the last byte records the pattern id (out).
2. Failure link of a node = the node for the longest proper suffix of its string that is also a trie prefix; depth-1 nodes fail to the root. BFS from the root: fail[child via b] = goto(fail[parent], b).
3. Dictionary (output) link of a node = the nearest node on its failure chain that ends a pattern. Walking these links lists all patterns ending at the current position, skipping silent nodes.
4. DFA conversion: in the same BFS, replace every missing edge by the failing node's edge (next[s][b] = next[fail[s]][b]). Failure links are then never followed at scan time.
5. Scan: s = next[s][byte]; if s or its dictionary chain has outputs, emit (pattern, end - len, end) for each.
6. Streaming: return s after each chunk and pass it to the next call. A match straddling the boundary completes in the second chunk.
7. Match semantics: step 5 gives all overlapping matches; for he, she, his, hers over ushers, she and he end at 4, hers at 6 (the 1975 paper's example, from memory). Leftmost-longest = sort by start, longest first, drop covered ones.

Code

const NONE: u32 = u32::MAX;

/// Aho-Corasick as a dense DFA over byte classes: `next[s*nc + class[b]]` is the full transition.
pub struct Ac {
    class: [u8; 256], // bytes that occur in no pattern share class 0 (an all-fail column)
    nc: usize,
    next: Vec<u32>,
    out: Vec<u32>,  // pattern id ending exactly at state s, or NONE
    dict: Vec<u32>, // nearest proper-suffix state that has an output, or NONE
    len: Vec<usize>,
}
impl Ac {
    pub fn new(pats: &[&[u8]]) -> Ac { // patterns must be non-empty
        let mut class = [0u8; 256];
        let mut nc = 1;
        for &b in pats.iter().flat_map(|p| p.iter()) {
            if class[b as usize] == 0 { class[b as usize] = nc as u8; nc += 1; } // <= 255 distinct bytes
        }
        // 1. trie (0 = "no child": the root is never a child)
        let mut next = vec![0u32; nc];
        let mut out = vec![NONE];
        for (id, p) in pats.iter().enumerate() {
            let mut s = 0usize;
            for &b in *p {
                let k = s * nc + class[b as usize] as usize;
                if next[k] == 0 {
                    next[k] = out.len() as u32;
                    out.push(NONE);
                    next.extend(std::iter::repeat(0).take(nc));
                }
                s = next[k] as usize;
            }
            if out[s] == NONE { out[s] = id as u32; } // duplicate pattern: first id wins
        }
        // 2. BFS: failure links, dictionary links, and the DFA fill-in
        let n = out.len();
        let (mut fail, mut dict) = (vec![0u32; n], vec![NONE; n]);
        let mut queue: std::collections::VecDeque<u32> = Default::default();
        for b in 0..nc {
            let c = next[b];
            if c != 0 { queue.push_back(c); } // depth-1 states fail to the root
        }
        while let Some(s) = queue.pop_front() {
            let s = s as usize;
            let f = fail[s] as usize;
            dict[s] = if out[f] != NONE { f as u32 } else { dict[f] };
            for b in 0..nc {
                let c = next[s * nc + b];
                let via_fail = next[f * nc + b]; // f is shallower: already complete
                if c != 0 {
                    fail[c as usize] = via_fail;
                    queue.push_back(c);
                } else {
                    next[s * nc + b] = via_fail; // missing edge = follow fail chain once, now
                }
            }
        }
        let len = pats.iter().map(|p| p.len()).collect();
        Ac { class, nc, next, out, dict, len }
    }
    /// Feed one chunk from `state`; call `f(pattern, start, end)` (absolute offsets, end
    /// exclusive) for every occurrence, overlapping included. `base` = bytes already fed.
    /// Returns the state to carry into the next chunk.
    pub fn feed(&self, mut s: u32, chunk: &[u8], base: usize, f: &mut impl FnMut(usize, usize, usize)) -> u32 {
        for (i, &b) in chunk.iter().enumerate() {
            s = self.next[s as usize * self.nc + self.class[b as usize] as usize];
            let mut m = if self.out[s as usize] != NONE { s } else { self.dict[s as usize] };
            while m != NONE {
                let p = self.out[m as usize] as usize;
                f(p, base + i + 1 - self.len[p], base + i + 1);
                m = self.dict[m as usize];
            }
        }
        s
    }
}

/// Word filter: fold byte-for-byte (offsets stay valid), match, then check word boundaries.
fn fold(b: u8) -> u8 {
    match b.to_ascii_lowercase() {
        b'0' => b'o', b'1' => b'i', b'3' => b'e', b'4' => b'a',
        b'5' | b'$' => b's', b'7' => b't', b'@' => b'a', c => c,
    }
}
pub fn banned_hits(ac: &Ac, text: &str) -> Vec<(usize, usize)> {
    let t: Vec<u8> = text.bytes().map(fold).collect();
    let is_word = |i: usize| t[i].is_ascii_lowercase();
    let mut hits = vec![];
    ac.feed(0, &t, 0, &mut |_, s, e| {
        if (s == 0 || !is_word(s - 1)) && (e == t.len() || !is_word(e)) { hits.push((s, e)); }
    });
    hits
}

#[test]
fn tests() {
    let ac = Ac::new(&[b"he", b"she", b"his", b"hers"]); // Aho & Corasick 1975 example
    let mut got = vec![];
    ac.feed(0, b"ushers", 0, &mut |p, s, e| got.push((p, s, e)));
    assert_eq!(got, [(1, 1, 4), (0, 2, 4), (3, 2, 6)]); // she, he (suffix of she), hers
    let (mut got, mut s) = (vec![], 0); // chunked: "she" straddles the boundary
    for (base, c) in [(0, &b"ush"[..]), (3, &b"ers"[..])] {
        s = ac.feed(s, c, base, &mut |p, st, e| got.push((p, st, e)));
    }
    assert_eq!(got, [(1, 1, 4), (0, 2, 4), (3, 2, 6)]);
    let bad = Ac::new(&[b"ass"]); // word filter: class, bass, assassin are not hits
    assert_eq!(banned_hits(&bad, "Classic ASS and a$$ in bass, assassin"), [(8, 11), (16, 19)]);
    assert!(banned_hits(&bad, "Passage").is_empty());
}

Complexity and constants

• Build: O(Σ|p| × nc) for nc byte classes. Table = states × nc × 4 bytes; states ≤ Σ|p| + 1. Measured on this Mac (Apple M4 Pro): 1,000 random patterns of 4-12 lowercase letters give 6,560 states, nc = 27, a 691 KiB table, built in under 3 ms.
• Scan: one dependent load per byte (the chain s → next[s] cannot be pipelined) plus one out check; pattern count enters only through cache footprint.
• Output bound: patterns a, aa, aaa, … over aaaa… give z ≈ n × k matches.

Efficiency

• Cost: measured on this Mac (Apple M4 Pro, one core, other jobs running at load average about 8, so a floor): 1,000 random patterns over 64 MiB of random lowercase text, 13,779 matches: 130 MB/s with 256-wide rows, 222-246 MB/s with 27 byte classes (3 runs each). About 4 ns per byte, bound by table load latency. Memory 691 KiB with classes, 6 MiB with 256-wide rows.
• Levers:
  • byte classes (bytes absent from all patterns share one column) — measured 130 → 222-246 MB/s above (smaller rows; cause not profiled) — small effective alphabet
  • full DFA instead of an NFA walk — crate docs: DFA fastest to search with "exorbitant" memory, contiguous NFA a little slower with excellent memory (docs.rs) — up to a few thousand patterns on hot paths
  • SIMD prefilter (Teddy) before the automaton — design notes: often an order of magnitude faster than Aho-Corasick alone (DESIGN.md) — few patterns, long haystacks, rare matches
  • fold once, not per pattern — one case-folded copy of the text replaces case variants of every pattern — case-insensitive lists
  • slices overlapping by max pattern length − 1, one per core — scales with cores (not measured) — large files
• Naive → standard → state of the art:
  • k separate substring searches · O(k·n)
  • Aho-Corasick DFA with byte classes · O(n + z), about 230 MB/s here at 1,000 patterns
  • SIMD packed matcher (Teddy) confirming candidates, automaton as fallback · often much faster on few patterns (aho-corasick crate); Hyperscan/Vectorscan add regex sets

Implementation notes

• Layouts. Dense rows (nc × u32) are fastest. Sparse edge lists per node save memory but add a search per byte; a hybrid keeps dense rows only for shallow levels (the crate's dense_depth option). Double-array tries (daachorse) give compact tables. u32 state ids halve the table versus usize.
• Word filter (usernames, chat). Normalise first and keep a map from folded to original offsets: Unicode NFKD, drop combining marks, case-fold, map look-alikes and leetspeak (confusables, text normalisation), collapse repeats, strip inserted separators. Then match with overlapping semantics and test word boundaries on each hit. The code folds byte-for-byte, so it needs no map.
• Boundaries. A hit counts only if both neighbours are not letters; this keeps "ass" out of "class" and "assassin" (the Scunthorpe problem: a block-list rejecting a place name). Check after matching rather than using leftmost matching, so a rejected short hit never hides a longer banned word. Scripts without spaces (Chinese, Japanese, Thai) have no such boundaries: segment first or accept substring hits plus an allow-list.

Pitfalls

• Filtering folded text but reporting offsets into the original: they shift after NFKD or multi-byte folding.
• Leftmost match kinds in the crate reject overlapping and streaming searches.
• Dense 256-wide table on a huge dictionary: 1 KiB per state; use classes or a contiguous NFA.
• A normaliser in front of a chunked scan must carry its own state (a UTF-8 character cut at the boundary).
• A word list is a policy, not a classifier: leet and spacing variants multiply; keep an allow-list.

Variants and alternatives

In production

Username and chat moderation; Suricata's default multi-pattern matcher is ac (docs list ac, ac-ks, hs); Rust's regex crate and ripgrep use the Rust crate for literal sets; sequencing pipelines scanning reads for adapter or motif sets; entity gazetteers; antivirus signature scanning.

Implementations

Sources

• A. V. Aho, M. J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM 18(6), 1975, pp. 333-340. paper
• A. Gallant, aho-corasick crate: MatchKind, AhoCorasickKind, DESIGN.md. docs · design · code
• X. Wang et al., Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs, NSDI 2019. paper
• Suricata documentation, Tuning considerations (mpm-algo). docs