简单复习了以下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;
}
