← all categories

Aho Corasick b60006fe

Aho-Corasick automaton over lowercase letters: add() each pattern (id < 32, tracked via bitmask), then build(). After build(), next[c] is a full O(1) transition table (no need to follow fail links while matching); out is a bitmask of pattern ids ending at this state or any of its suffix-link ancestors.

Time: O(sum(|pattern|) \cdot 26) build; O(|text|) to run. tested

content/strings/aho-corasick.h

struct AhoCorasick {
    struct Node {
        int next[26], link = 0, out = 0;
        Node() { fill_n(next, 26, -1); }
    };
    vector<Node> t;
    AhoCorasick() { t.emplace_back(); }

    void add(string &s, int id) {
        int at = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[at].next[c] == -1) { t[at].next[c] = (int)t.size(); t.emplace_back(); }
            at = t[at].next[c];
        }
        t[at].out |= (1 << id);
    }

    void build() {
        queue<int> q;
        for (int c = 0; c < 26; c++) {
            int at = t[0].next[c];
            if (at != -1) { t[at].link = 0; q.push(at); }
            else t[0].next[c] = 0;
        }
        while (!q.empty()) {
            int at = q.front(); q.pop();
            t[at].out |= t[t[at].link].out;
            for (int c = 0; c < 26; c++) {
                int to = t[at].next[c];
                if (to != -1) { t[to].link = t[t[at].link].next[c]; q.push(to); }
                else t[at].next[c] = t[t[at].link].next[c];
            }
        }
    }
};