Dictionaries, Tries & Multiple-Pattern Search

Trie Fundamentals and Child Representations

A trie stores dictionary keys by sharing prefixes along root-to-node paths. Each edge consumes one symbol, each node represents the prefix spelled by its path, and a terminal count distinguishes complete keys from prefixes of longer keys. A subtree count supports prefix-frequency queries and safe pruning after deletion.

For a key of length $m$, insertion and lookup inspect $m$ symbols. Deletion clears or decrements the terminal count, updates counts on the path, and removes a node only when it is nonterminal and has no live descendants. Autocomplete first reaches the prefix node in $O(p)$ time, then traverses its subtree; visiting children in alphabet order produces lexicographic output. Reporting $z$ output symbols necessarily adds $O(z)$ work.

Here $d$ is node degree and $w$ is machine-word size. Hybrid tries can start with a small sorted vector and promote high-degree nodes to a bitmap or hash map.

Compressed and Persistent Dictionary Structures

A radix tree compresses every maximal unary path into one edge labeled by a non-empty string. Lookup compares the query with edge labels; insertion splits an edge at the first mismatch, and deletion merges adjacent edges when a nonterminal unary node remains. Compression reduces nodes and pointer chasing without changing the represented key set.

A Patricia trie records only discriminating bit positions, making it especially useful for binary keys. A ternary search tree stores one symbol with lower, equal, and higher branches, avoiding alphabet-sized arrays while retaining ordered traversal. A persistent trie uses path copying, allocating $O(m)$ nodes per length-$m$ update while sharing untouched subtrees. Static dictionaries can use succinct LOUDS bitvectors with rank/select navigation or minimal acyclic automata that merge equivalent suffix subtrees.

Building the Aho-Corasick Automaton

Aho-Corasick first inserts all patterns into a trie. Each terminal node stores the identifiers of patterns ending there. A failure link from state $u$ points to the state representing the longest proper suffix of $u$'s path string that is also a trie prefix.

Failure links are built breadth-first. The root fails to itself, and every depth-one state fails to the root. For each edge $v\xrightarrow{c}u$, follow failures from $\operatorname{fail}(v)$ until a state with a $c$ transition is found or the root is reached; that transition determines $\operatorname{fail}(u)$. Outputs may be copied from failure states for fast reporting or connected through output links to save memory.

flowchart TD
    R["root"] -->|"s"| S["s"]
    S -->|"h"| SH["sh"]
    SH -->|"e"| SHE["she: output she"]
    R -->|"h"| H["h"]
    H -->|"e"| HE["he: output he"]
    S -. "failure" .-> R
    SH -. "failure" .-> H
    SHE -. "failure and output suffix" .-> HE
    H -. "failure" .-> R
    HE -. "failure" .-> R

After every processed text prefix, the active state represents its longest suffix that is also a pattern prefix. This invariant preserves overlapping matches without restarting the scan.

Reporting, Counting, and Automaton DP

For each text symbol, follow failure links until a matching transition exists or the root is reached, take that transition, and emit the resulting state's outputs. If total pattern length is $M$, text length is $n$, and $z$ occurrences are returned, the full cost is $O(M+n+z)$. The $z$ term is unavoidable when occurrences are explicitly materialized.

If only a total count is needed, precompute the number of direct and inherited outputs at each state; each scanned symbol then contributes one value in $O(1)$ time. For per-pattern totals, count visits to automaton states and propagate them upward through the failure tree in reverse breadth-first order. Automaton DP can also count length-$L$ strings that avoid forbidden patterns by using states $(i,u)$ and rejecting transitions into output states.

from collections import deque


class AhoCorasick:
    def __init__(self, patterns):
        self.patterns = list(patterns)
        self.next = [{}]
        self.fail = [0]
        self.output = [[]]

        for pattern_id, pattern in enumerate(self.patterns):
            if not pattern:
                raise ValueError("empty patterns require an explicit policy")
            state = 0
            for char in pattern:
                if char not in self.next[state]:
                    self.next[state][char] = len(self.next)
                    self.next.append({})
                    self.fail.append(0)
                    self.output.append([])
                state = self.next[state][char]
            self.output[state].append(pattern_id)

        queue = deque(self.next[0].values())
        while queue:
            state = queue.popleft()
            for char, child in self.next[state].items():
                fallback = self.fail[state]
                while fallback and char not in self.next[fallback]:
                    fallback = self.fail[fallback]
                self.fail[child] = self.next[fallback].get(char, 0)
                self.output[child].extend(self.output[self.fail[child]])
                queue.append(child)

    def find_all(self, text):
        """Return (start, end, pattern_id, pattern), using inclusive indices."""
        state = 0
        matches = []
        for end, char in enumerate(text):
            while state and char not in self.next[state]:
                state = self.fail[state]
            state = self.next[state].get(char, 0)
            for pattern_id in self.output[state]:
                pattern = self.patterns[pattern_id]
                matches.append((end - len(pattern) + 1, end, pattern_id, pattern))
        return matches

    def count_all(self, text):
        state = total = 0
        for char in text:
            while state and char not in self.next[state]:
                state = self.fail[state]
            state = self.next[state].get(char, 0)
            total += len(self.output[state])
        return total


if __name__ == "__main__":
    matcher = AhoCorasick(["he", "she", "his", "hers"])
    assert [(a, b, p) for a, b, _, p in matcher.find_all("ushers")] == [
        (1, 3, "she"), (2, 3, "he"), (2, 5, "hers")
    ]
    assert AhoCorasick(["a", "aa"]).count_all("aaa") == 5

Choosing a Dictionary Structure

Use a trie or radix tree for prefix lookup, autocomplete, and segmentation; ordered children or cached top suggestions improve ranked enumeration. Spell-checking can traverse a trie while carrying edit-distance states. Fixed-width binary tries support maximum- and minimum-XOR queries by choosing the preferred bit at each level. Persistent tries support historical queries, while succinct tries, sorted arrays, or minimal acyclic automata suit large static dictionaries.

Aho-Corasick is the natural choice when many stable exact patterns must be scanned against the same text or stream. A hash set is usually simpler for exact membership without prefix queries. Ternary search trees suit sparse ordered alphabets, while continuously changing pattern sets or approximate matching may require different indexes.