【模板】AC自动机.cpp

/*** 朴素AC自动机 ***/
struct node {
    static const int sigma_size = 2;
    array<int, sigma_size> pos{};
    bool is_accept_state = false;
    int suffix_pos = 0;
};

vector<node> trie;
void insert(const int* s, int len) {
    int cur = 0;
    rng (i, 0, len) {
        if (!trie[cur].pos[s[i]]) {
            trie[cur].pos[s[i]] = SZ(trie);
            trie.pb({});
        }
        cur = trie[cur].pos[s[i]];
    }
    trie[cur].is_accept_state = true;
}

// c: character
int go(int cur, int c) {
    while (cur != 0 && trie[cur].pos[c] == 0) {
        cur = trie[cur].suffix_pos;
    }
    return trie[cur].pos[c];
}

void build_AC_automata() {
    queue<int> que;
    for (int i = 0; i < node::sigma_size; ++i) {
        if (trie[0].pos[i]) {
            que.push(trie[0].pos[i]);
        }
    }
    while (!que.empty()) {
        auto par = que.front();
        que.pop();
        rng (c, 0, node::sigma_size) {
            int u = trie[par].pos[c];
            if (u) {
                que.push(u);
                trie[u].suffix_pos = go(trie[par].suffix_pos, c);
            }
        }
    }
}




/*** 优化版 AC自动机（把所有不存在的边补上）***/
struct node {
    static const int sigma_size = 2;
    array<int, sigma_size> pos{};
    bool is_accept_state = false;
    int suffix_pos = 0;
};

vector<node> trie;
void insert(const int* s, int len) {
    int cur = 0;
    rng (i, 0, len) {
        if (!trie[cur].pos[s[i]]) {
            trie[cur].pos[s[i]] = SZ(trie);
            trie.pb({});
        }
        cur = trie[cur].pos[s[i]];
    }
    trie[cur].is_accept_state = true;
}

void build_AC_automata() {
    queue<int> que;
    for (int i = 0; i < node::sigma_size; ++i) {
        if (trie[0].pos[i]) {
            que.push(trie[0].pos[i]);
        }
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        rng (c, 0, node::sigma_size) {
            int& v = trie[u].pos[c];
            if (v) {
                que.push(v);
            }
            // 把不存在的边补上
            (v ? trie[v].suffix_pos : v) = trie[trie[u].suffix_pos][c];
        }
    }
}