洛谷5357 AC自动机模板 二次加强 复习

简单复习了以下AC自动机。

首先注意，$$n$$个字符串构建的AC自动机至多可能有总串长+1个节点（根节点不隶属于任何一个字符串）

由fail指针构成的树叫做后缀链接树，每个点的父节点为这个点所表示的字符串，在整个ACAM里能匹配到的公共后缀最长的字符串。（与SAM里的后缀连接好像是一样的….）

构建后缀链接，并且把Trie树补成Trie图（即将每个点的不存在的子节点指向下一个待匹配位置的操作）通过BFS进行。

初始时： 根节点的子节点的fail指针全都指向根，根节点的不存在的子节点构造关于根的自环。

接下来根节点的存在的子节点入队，开始BFS。

从队列里取出来队首元素V，按照如下方法操作：

遍历其子节点，设当前遍历到的子节点通过字符chr获得，如果这个子节点存在，则其后缀链接指向V的后缀链接指向的节点的chr子节点，并将该节点入队。

如果该子节点不存在，则将其替换为V的后缀链接的chr子节点。

如果遇到一个所有字符串都没出现的字符怎么办？这时我们肯定会走到根，然后沿着根节点的子节点走自环，成功滚到下一个字符。

匹配时直接沿着Trie图走即可（我们在BFS中已经把所有点的子节点补完了），每走到一个点，则说明了我们匹配到了根到这个点的边所构成的字符串。

然后怎么统计每个子串出现的次数呢？

首先我们在ACAM上的每个点标记上以这个点结尾的字符串，可以知道这种标记只会有总字符串个数个。

然后我们构建出后缀链接树，我们可以知道，当我们的字符串走到某个点的时候，就意味着匹配到了这个点在后缀链接树上到树根经历的所有字符串，然后我们打个到根的差分标记，最后DFS统计下标记即可求出来每个字符串访问了几遍。

#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

struct Node {
    Node* chd[26];
    Node* fail = nullptr;
    // std::vector<int_t> strs;
    std::vector<int_t> strs;
    int_t mark = 0;
    Node*& access(char x) { return chd[x - 'a']; }
    Node() { memset(chd, 0, sizeof(chd)); }
    int_t id;
};
std::vector<int_t> graph[int_t(2e5) + 10];

Node* mapping[int_t(2e5) + 10];
Node* root = new Node;
int_t used = 1;
void insert(const char* str, int_t id) {
    Node* curr = root;
    for (auto ptr = str; *ptr; ptr++) {
        auto& chd = curr->access(*ptr);
        if (chd == nullptr) {
            chd = new Node;
            chd->id = ++used;
            mapping[used] = chd;
        }
        curr = chd;
    }
    curr->strs.push_back(id);
}
void buildFail() {
    std::queue<Node*> queue;
    // 安排根节点的子节点
    for (auto& ref : root->chd) {
        if (ref) {
            ref->fail = root;
            queue.push(ref);
            graph[1].push_back(ref->id);
        } else {
            ref = root;
        }
    }
    while (!queue.empty()) {
        Node* front = queue.front();
        queue.pop();
        for (char chr = 'a'; chr <= 'z'; chr++) {
            auto& ptr = front->access(chr);
            if (ptr) {
                queue.push(ptr);
                ptr->fail = front->fail->access(chr);
                graph[ptr->fail->id].push_back(ptr->id);
#ifdef DEBUG
                cout << "edge " << ptr->fail->id << " to " << ptr->id << endl;
#endif
            } else {
                ptr = front->fail->access(chr);
            }
        }
    }
}
int_t counts[int_t(2e5 + 1)];
void DFS(int_t vtx) {
    for (auto chd : graph[vtx]) {
        DFS(chd);
        mapping[vtx]->mark += mapping[chd]->mark;
    }
    Node* curr = mapping[vtx];
    for (auto x : curr->strs) {
        counts[x] += curr->mark;
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    root->id = 1;
    mapping[1] = root;
    int_t n;
    cin >> n;
    static char buf[int_t(3e6 + 10)];
    for (int_t i = 1; i <= n; i++) {
        cin >> buf;
        insert(buf, i);
    }
    buildFail();
    cin >> buf;
    auto curr = root;

    for (auto ptr = buf; *ptr; ptr++) {
        auto chd = curr->access(*ptr);
        chd->mark += 1;
        curr = chd;
    }
    DFS(1);
    for (int_t i = 1; i <= n; i++)
        cout << counts[i] << endl;
    return 0;
}