iv. Trie and Aho-Corasick

A trie stores strings as root-to-node paths (insert / lookup $O(|w|)$ independent of the number of words, prefix counts, lexicographic order). Aho–Corasick adds suffix (failure) links and turns the trie into an automaton that finds all occurrences of many patterns in one pass, $O(n+m+\text{matches})$, and supports DP over “which patterns have I just completed”. The bitwise trie for XOR problems is Binary Trie.

Query	Structure	Cost
is $w$ stored; longest stored prefix of $w$	trie	$O(|w|)$
how many words start with $p$; all of them (autocomplete)	trie with pass counts	$O(|p|)$, $+$ output
$k$-th word lexicographically	trie with subtree counts	$O(|w|\sigma )$
distinct substrings	trie of all suffixes $O(n^2)$; use a suffix automaton for $O(n)$
occurrences of each of many patterns in a text	Aho–Corasick + counts summed up the link tree	$O(n+m\sigma )$
list all (position, pattern) matches	Aho–Corasick with dictionary (output) links	$O(n+m\sigma +\text{matches})$
strings of length $L$ avoiding all patterns / containing one	DP over automaton states; matrix power for huge $L$	$O(Lm\sigma )$ / $O(m^3\log L)$
patterns inserted and deleted online (CF 710F)	binary grouping of static automata	$O(L\log L\cdot \sigma )$ total

	trie	hash set
lookup	$O(|w|)$	$O(|w|)$ hashing
prefix queries, ordered iteration	yes	no
memory	high: $\sum |w|\cdot \sigma$ ints with arrays (104 MB for $10^6$ characters, $\sigma =26$)	low

Memory relief: map children ($O(\log \sigma )$ lookups), or a compressed trie (radix / Patricia tree: chains of single-child nodes become one edge labelled by a substring; $O(\#\text{words})$ nodes, insertion splits edges). A suffix tree is the compressed trie of all suffixes. Deletion: decrement the pass counts (a zero count behaves as absent). Related: suffix automaton (a DAG with linear size over all substrings), eertree (a trie over palindromes), persistent tries.

struct Trie {
    vector<array<int, 26>> nxt; vector<int> pass, ends;     // words through / ending at a node
    Trie() { newNode(); }
    int newNode() { nxt.push_back({}); nxt.back().fill(-1); pass.push_back(0); ends.push_back(0); return sz(nxt) - 1; }
    void insert(const string& s, int d = 1) {             // d = -1 erases one copy (must be present)
        int v = 0; pass[v] += d;
        for (char ch : s) { int c = ch - 'a'; if (nxt[v][c] == -1) nxt[v][c] = newNode(); v = nxt[v][c]; pass[v] += d; }
        ends[v] += d;
    }
    int walk(const string& p) const { int v = 0; for (char ch : p) { v = nxt[v][ch - 'a']; if (v == -1) return -1; } return v; }
    bool contains(const string& s) const { int v = walk(s); return v != -1 && ends[v] > 0; }
    int countPrefix(const string& p) const { int v = walk(p); return v == -1 ? 0 : pass[v]; }
    int longestStoredPrefix(const string& w) const {        // length of the longest stored word that is a prefix of w, -1 if none
        int v = 0, best = ends[0] > 0 ? 0 : -1;
        for (int i = 0; i < sz(w); i++) { v = nxt[v][w[i] - 'a']; if (v == -1) break; if (ends[v] > 0) best = i + 1; }
        return best;
    }
    string kth(int k) const {                               // k-th (0-indexed) stored word in lexicographic order, with multiplicity
        string res; int v = 0;
        while (true) {
            if (k < ends[v]) return res;
            k -= ends[v];
            for (int c = 0; c < 26; c++) { int u = nxt[v][c]; if (u == -1 || pass[u] <= 0) continue; if (k < pass[u]) { res += 'a' + c; v = u; break; } k -= pass[u]; }
        }
    }
};
 
struct AhoCorasick {                                        // lowercase patterns, full goto automaton
    vector<array<int, 26>> go; vector<int> link, out, termOf, order; vector<vector<int>> endsHere;
    int addPattern(const string& s, int id) {
        if (go.empty()) newNode();
        int v = 0;
        for (char ch : s) { int c = ch - 'a'; if (!go[v][c]) { int u = newNode(); go[v][c] = u; } v = go[v][c]; }
        endsHere[v].push_back(id); termOf.push_back(v); return v;
    }
    int newNode() { go.push_back({}); link.push_back(0); out.push_back(-1); endsHere.push_back({}); return sz(go) - 1; }
    void build() {                                          // BFS; out[v] = nearest node on the link chain (excluding v) where a pattern ends
        if (go.empty()) newNode();
        order = {0};
        for (int i = 0; i < sz(order); i++) {
            int v = order[i];
            for (int c = 0; c < 26; c++) {
                int u = go[v][c];
                if (u) {                                    // tree edge (the root is never a child)
                    link[u] = v == 0 ? 0 : go[link[v]][c];
                    out[u] = endsHere[link[u]].empty() ? out[link[u]] : link[u];
                    order.push_back(u);
                } else go[v][c] = v == 0 ? 0 : go[link[v]][c];
            }
        }
    }
    vector<ll> countOccurrences(const string& text, int numPatterns) {   // occurrences of each pattern, O(n + m)
        vector<ll> hit(sz(go), 0); int v = 0;
        for (char ch : text) { v = go[v][ch - 'a']; hit[v]++; }
        for (int i = sz(order) - 1; i > 0; i--) hit[link[order[i]]] += hit[order[i]];   // push counts up the link tree
        vector<ll> res(numPatterns, 0); for (int id = 0; id < numPatterns; id++) res[id] = hit[termOf[id]];
        return res;
    }
    vector<pair<int, int>> allMatches(const string& text) { // (end position, pattern id)
        vector<pair<int, int>> res; int v = 0;
        for (int i = 0; i < sz(text); i++) {
            v = go[v][text[i] - 'a'];
            for (int u = endsHere[v].empty() ? out[v] : v; u > 0; u = out[u]) for (int id : endsHere[u]) res.push_back({i, id});
        }
        return res;
    }
    ll countAvoiding(int L, int A, ll mod) {                // strings of length L over the first A letters containing no pattern
        int n = sz(go); vector<char> bad(n, 0);
        for (int v : order) bad[v] = !endsHere[v].empty() || (v && bad[link[v]]);
        vector<ll> dp(n, 0); dp[0] = 1;
        for (int i = 0; i < L; i++) {
            vector<ll> nd(n, 0);
            for (int v = 0; v < n; v++) if (dp[v]) for (int c = 0; c < A; c++) { int u = go[v][c]; if (!bad[u]) nd[u] = (nd[u] + dp[v]) % mod; }
            dp = nd;
        }
        ll r = 0; for (ll x : dp) r = (r + x) % mod; return r;
    }
};

Proof: trie queries and the Aho–Corasick invariants

Trie. A node is a prefix; pass counts stored words having it as a prefix, ends those equal to it; the $k$-th word walk skips whole subtrees in lexicographic order (words ending at a node come before its extensions). Suffix links. For a node (string) $v$, link[v] is the longest proper suffix of $v$ that is a trie node. BFS processes nodes by depth; for $u=vc$, the candidates are $wc$ for suffixes $w$ of $v$ that are nodes, tried from the longest, and go[link[v]][c] already encodes that search (by induction it is the longest suffix of $\mathrm{link}[v]c$ that is a node). Missing edges are filled as go[v][c] = go[link[v]][c], which makes go the transition function of the DFA. Invariant: after reading text $t_0..t_i$ the state is the longest suffix of the text read that is a trie node (as in KMP). A pattern $P$ ends at $i$ iff $P$ is a suffix of the text read and a node, iff $P$ lies on the suffix-link chain of the current state (every suffix of the state that is a node is on its chain). Counting: the number of times $P$ ends somewhere equals the number of visits to states whose chain contains $P$‘s node, i.e. the sum of visit counts over the link subtree of that node, accumulated in reverse BFS order (children of the link tree are deeper). Output links skip chain nodes where no pattern ends, so listing costs $O(1)$ per match plus one step. Avoiding: a state is bad iff some pattern ends on its chain; strings avoiding all patterns are exactly the walks that never enter a bad state. Build is $O(m\sigma )$. Verified against brute-force substring search for random pattern sets.

Dynamic Aho–Corasick

Patterns are inserted and deleted online and queries ask for the total number of occurrences of the current patterns in a text (CF 710F). Keep groups of sizes $2^k$ like a binary counter (static-to-dynamic); each group is a static automaton whose cnt[v] is the number of patterns ending on the link chain of $v$. Deletions go into a second structure and are subtracted.

struct DynamicAhoCorasick {
    struct Static {
        vector<array<int, 26>> go; vector<int> link, cnt; vector<string> pats;
        void build() {
            go.assign(1, {}), link.assign(1, 0), cnt.assign(1, 0);
            for (auto& p : pats) {
                int v = 0;
                for (char ch : p) { int c = ch - 'a'; if (!go[v][c]) { go[v][c] = sz(go); go.push_back({}), link.push_back(0), cnt.push_back(0); } v = go[v][c]; }
                cnt[v]++;
            }
            vector<int> q; for (int c = 0; c < 26; c++) if (go[0][c]) q.push_back(go[0][c]);
            for (int i = 0; i < sz(q); i++) {
                int v = q[i]; cnt[v] += cnt[link[v]];
                for (int c = 0; c < 26; c++) { int u = go[v][c]; if (u) link[u] = go[link[v]][c], q.push_back(u); else go[v][c] = go[link[v]][c]; }
            }
        }
        ll count(const string& text) const { if (pats.empty()) return 0; ll res = 0; int v = 0; for (char ch : text) { v = go[v][ch - 'a']; res += cnt[v]; } return res; }
    };
    struct Grouped {
        vector<Static> groups;
        void insert(const string& p) {
            vector<string> cur = {p}; int k = 0;
            while (k < sz(groups) && !groups[k].pats.empty()) { cur.insert(cur.end(), all(groups[k].pats)); groups[k] = Static(); k++; }
            if (k == sz(groups)) groups.emplace_back();
            groups[k].pats = move(cur); groups[k].build();
        }
        ll count(const string& text) const { ll r = 0; for (auto& g : groups) r += g.count(text); return r; }
    };
    Grouped added, removed;
    void insert(const string& p) { added.insert(p); }
    void erase(const string& p) { removed.insert(p); }       // p must currently be present
    ll count(const string& text) const { return added.count(text) - removed.count(text); }
};

Proof: binary grouping

Occurrence counts are additive over pattern multisets, so the answer is (count over everything inserted) minus (count over everything erased), and each side is a sum over its groups. In each structure, group $k$ holds at most $2^k$ patterns; an insertion merges groups $\mathrm{0..}k-1$ into group $k$ like incrementing a binary counter, so every pattern is rebuilt at most ${\log }_2$ (number of insertions) times, giving $O(L\log L\cdot \sigma )$ total build time, and a query visits $O(\log L)$ groups. Within a group, cnt[v] accumulated along links counts the patterns ending at the current text position by the Aho–Corasick invariant. Checked against brute force under random insert / erase / query sequences.

Binary trie (pointer)

The trie over bits of integers (most significant first) answers XOR queries by greedy walks; full treatment and code in Binary Trie.

Query	Method
max / min of $x\oplus y$ over stored $y$	walk the opposite / same bit
count stored $y$ with $x\oplus y<K$ ($\ge K$)	at each 1-bit of $K$ add the subtree on the matching side, descend the other (complement)
$k$-th smallest $x\oplus y$, $k$-th stored value, count $<v$	subtree counts
maximum XOR subarray / pair	prefix XORs inserted one by one
subarrays with XOR in $[L,R]$	$f(R+1)-f(L)$ with $f(K)$ = count below $K$
XOR with a bound $y\le M$	walk with a tight flag as in digit DP
max XOR with any element of $a[l..r]$	persistent trie, counts differenced between versions

	binary trie	XOR basis
stores	a multiset of values	a linear span
max XOR over all subsets	no	yes
count values with a property, deletion	yes	no / hard
memory	$O(nB)$	$O(B)$

“Choose an element” wants the trie, “choose a subset” wants the XOR basis. The greedy is optimal because $2^b>{\sum }_{i<b}{2}^i$.

Related notes

• Prefix Function and Z (the single-pattern automaton)
• Binary Trie
• Matrix Exponentiation DP (automaton + matrix power)