浅谈 AC 自动机 / ACAM

kaikai_qwq · 2026-08-27 20:34:48 · 算法·理论

::::info[自动机是什么？]

根据 oi-wiki 整理

自动机的数学定义是一个五元组，它精确地描述了一个离散的、状态驱动的计算模型。

其形式化定义如下：

一个确定有限状态自动机（DFA） 由一个五元组 (Q, \Sigma, \delta, q_0, F) 构成：

1. Q：一个有限的状态集合。
2. \Sigma：一个有限的输入字母表（字符集）。
3. \delta：转移函数，定义为 \delta: Q \times \Sigma \rightarrow Q。它描述了自动机在读取一个字符后，如何从当前状态唯一地转移到下一个状态。
4. q_0：起始状态，且 q_0 \in Q。
5. F：接受状态集合，且 F \subseteq Q。

AC 自动机可以解决一类多模匹配问题。

AC 自动机求解多模匹配问题的思想为：

把模式串插入到 Trie 中，通过构建类似 KMP 的失配指针（fail 指针），然后扫描文本串在 AC 自动机上匹配得到结果。

1 如何构建 AC 自动机

1.1 构建字典树

首先，我们需要将这若干个模式串插入到一个 Trie 中。

对于 Trie 树上每个位置，在自动机中的状态为 Trie 的根节点到当前节点的字符串。

以下用 (u, c) 表示 u Trie 上由 c 指向的节点。

1.2 如何求解 fail 指针

和 KMP 中的失配指针相比，AC 自动机的失配指针 fail_u 指向的为 Trie 树上的一个状态 v，满足 v 是 u 的最长后缀，也就是 u 在 Trie 树上的后缀状态中最长的那个。

考虑当前我们需要求解的位置为 u，父亲为 fa，有一条边 (fa, c) 指向 u，其中 c 是字符集中的字符，并且满足深度 < u 的节点已经求解完成。

首先，因为状态 u 相当于状态 fa 加上了一个字符 c，所以 u 的后缀都相当于：状态 fa 的后缀加上字符 c。

由于我们需要求的是最长后缀，那么最先尝试的肯定是 (fail_{fa}, c)，接下来考虑 (fail_{fa}, c) 是否存在。

• 若 (fail_{fa}, c) 存则，则 fail_u = (fail_{fa}, c)。
• 否则，我们不断尝试当前 fa 的次长后缀，也就是 fail_{fail_{fa}}，如果存在则 fail_u = (fail_{fail_{fa}}, c)，否则像这样一直跳。
• 跳到根则设为 0。

1.3 代码实现

构建字典树部分就不说了。

求解 fail 指针部分，由于我们需要小于当前深度的点全部求解完毕，所以使用 BFS 实现。

以下边默认是在未路径压缩的 Trie 中的边。

对于 (fail_{fa}, c) 存在的情况，则直接赋值即可。

对于 (fail_{fa}, c) 不存在的情况，你可以直接往上跳，但是这里介绍一种叫做路径压缩的方法，也叫建立字典图。

这种情况，我们要找的实际上就是 (fail^k(fa), c)。

首先我们建出一个 AC 自动机。

考虑查询，首先肯定要在字典树上匹配，此部分不讲，关键在于每到 T 中一个状态，如何查询。

我们不断跳当前状态 u 的 fail 指针，相当于不断跳 u 的最长有效后缀、次长有效后缀，如果当前跳到了一个模式串结尾，则统计答案。

::::success[完整代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int ch[MAXN][30];
int pos[MAXN];
int fail[MAXN];
int n, tot = 1;
string s, t[MAXN];
int cnt[MAXN];
void insert(string s, int P) {
    int u = 1;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        if (ch[u][c] == 0) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    pos[u] = P;
}
void get_fail() {
    for (int i = 0; i < 26; i++) ch[0][i] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int v = ch[u][i];
            if (v == 0) {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            fail[v] = ch[fail[u]][i];
            q.push(v);
        }
    }
}
void query(string s) {
    int u = 1;
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        u = ch[u][c];
        int tmp = u;
        while (tmp > 1) {
            if (pos[tmp]) cnt[pos[tmp]]++;
            tmp = fail[tmp];
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    while ("banana") {
        cin >> n;
        if (!n) break;
        for (int i = 0; i <= tot; i++) {
            memset(ch[i], 0, sizeof(ch[i]));
            fail[i] = pos[i] = cnt[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            cin >> t[i];
            insert(t[i], i);
        }
        get_fail();
        cin >> s;
        query(s);
        int res = 0;
        for (int i = 1; i <= n; i++) res = max(res, cnt[i]);
        cout << res << '\n';
        for (int i = 1; i <= n; i++)
            if (cnt[i] == res) cout << t[i] << '\n';
    }
    return 0;
}

::::

【模板】AC 自动机

给你一个文本串 S 和 n 个模式串 T_{1 \sim n}，请你分别求出每个模式串 T_i 在 S 中出现的次数。

1\le n\le 2\times 10^5, \sum_{i = 1}^n |T_i|\le 2\times 10^5, |S|\le 2\times 10^6

我们发现直接套用上一题会 TLE，这里介绍一种拓扑排序优化。

我们发现，AC 自动机复杂度瓶颈在于匹配时跳 fail。

因为 fail 显然不会有环，并且深度一定越来越低，所以我们如果只保留 AC 自动机中的 fail 边，会形成一棵树，这棵树称为 fail 树。

那么，我可以考虑，预先记录要跳那些，然后最后求和，即可优化效率。

那么，我们考虑按照 fail 树，做一次拓扑排序，一次性求出匹配次数。

由于需要拓扑排序，我们需要在求解 fail 时多统计入度。

查询时首先打上标记，然后拓扑排序求出答案。

::::success[完整代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
int ch[MAXN][30];
int pos[MAXN], idx[MAXN];
int fail[MAXN];
int n, tot = 1;
string s, t[MAXN];
int cnt[MAXN];
int in[MAXN];
int Get[MAXN];
void insert(string s, int &idx, int P) {
    int u = 1;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        if (ch[u][c] == 0) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    if (!pos[u]) pos[u] = P;//可能会有重复，所以需要去重
    idx = pos[u];
}
void get_fail() {
    for (int i = 0; i < 26; i++) ch[0][i] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int v = ch[u][i];
            if (v == 0) {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            fail[v] = ch[fail[u]][i];
            in[fail[v]]++;
            q.push(v);
        }
    }
}
void query(string s) {
    int u = 1;
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        u = ch[u][c];
        Get[u]++;
    }
}
void topu() {
    queue <int> q;
    for (int i = 0; i <= tot; i++)
        if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt[pos[u]] = Get[u];
        Get[fail[u]] += Get[u];
        if ((--in[fail[u]]) == 0) q.push(fail[u]);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        insert(t[i], idx[i], i);
    }
    get_fail();
    cin >> s;
    query(s);
    topu();
    for (int i = 1; i <= n; i++) cout << cnt[idx[i]] << '\n';
    return 0;
}

::::

3 例题

3.1 P2444 [POI 2000 R1] 病毒

给定 n 个危险的二进制串 s_1\sim s_n，如果一个二进制串是安全的，则其不包含任何一个危险的二进制子串，请你判断是否存在一个无限长的安全二进制串。

1\le n\le 2000, \sum_{i = 1}^n |s_i|\le 3\times 10^4

第一道例题放个水题吧qwq

对于一个安全的字符串，匹配一定匹配不到危险的串的结尾，也就是跳 fail 肯定跳不到一个危险串结尾。

于是，对于能跳 fail 跳到危险串的点，都是危险点。

由于要求无限，也就是匹配时一直在打转，那么就有环，所以只需要判断 AC 自动机中是否有安全的环即可 。

::::success[完整代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int ch[MAXN][30];
int pos[MAXN];
int fail[MAXN];
int n, tot = 1;
string s[MAXN];
int cnt[MAXN];
bool banana[MAXN], vis[MAXN], viss[MAXN]; 
void insert(string s, int P) {
    int u = 1;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - '0';
        if (ch[u][c] == 0) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    pos[u] = P;
    banana[u] = 1; 
}
void get_fail() {
    for (int i = 0; i < 2; i++) ch[0][i] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        banana[u] |= banana[fail[u]];
        for (int i = 0; i < 2; i++) {
            int v = ch[u][i];
            if (v == 0) {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            fail[v] = ch[fail[u]][i];
            q.push(v);
        }
    }
}
void dfs(int u) {
    if (vis[u]) {
        cout << "TAK";
        exit(0);
    }
    if (banana[u] || viss[u]) return;
    vis[u] = viss[u] = 1;
    dfs(ch[u][0]);
    dfs(ch[u][1]);
    vis[u] = 0;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        insert(s[i], i);
    }
    get_fail();
    dfs(0);
    cout << "NIE";
    return 0;
}

::::

3.2 P14363 [CSP-S 2025] 谐音替换 / replacee

自己去原题面看（）

我们设当前 t1, t2 的最长公共前缀为 L，最长公共后缀为 R。

那么替换一定需要覆盖 L, R 中间的那块区域，还可能覆盖 L, R，但是一定会与原来相同。

也就是一定形如：\texttt{LAR}\to \texttt{LBR}。

那么我们考虑把 t1, t2 合并成一个这样的字符串：\texttt{L?A?B?R}。

对于每个 s1, s2 也合并成这样的形式。

那么，我们发现，合法的替换中一定会满足 s1, s2 合并成的字符串是 t1, t2 合并成的字符串的子串。

这时候就变成了一个多模匹配问题，使用 AC 自动机解决。

注意需要特殊处理 s1, s2 相等和 t1, t2 相等，需要预处理 fail 链的和。

::::success[完整代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e6 + 10;
int ch[MAXN][30];
int pos[MAXN];
int fail[MAXN];
int n, q, tot = 1;
int cnt[2][MAXN];
int get(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    else if (c == '&') return 26;
    else if (c == '^') return 27;
    else return 28; 
}
void insert(int type, string s, int P) {
    int u = 1;
    for (int i = 0; i < s.size(); i++) {
        int c = get(s[i]);
        if (ch[u][c] == 0) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    pos[u] = P;
    cnt[type][u]++;
}
void get_fail() {
    for (int i = 0; i < 29; i++) ch[0][i] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt[0][u] += cnt[0][fail[u]];
        cnt[1][u] += cnt[1][fail[u]];
        for (int i = 0; i < 29; i++) {
            int v = ch[u][i];
            if (v == 0) {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            fail[v] = ch[fail[u]][i];
            q.push(v);
        }
    }
}
int query(int type, string s) {
    int u = 1;
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        int c = get(s[i]);
        u = ch[u][c];
        ans += cnt[type][u];
    }
    return ans;
}
string get(string a, string b) {
    if (a == b) return a;
    int n = a.size();
    int L = 0, R = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) {
            L = i;
            break;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] != b[i]) {
            R = i;
            break;
        }
    }
    string res = "";
    for (int i = 0; i < L; i++) res += a[i];
    res += '&';
    for (int i = L; i <= R; i++) res += a[i];
    res += '^';
    for (int i = L; i <= R; i++) res += b[i];
    res += '|';
    for (int i = R + 1; i < n; i++) res += b[i];
//  cout << res << '\n';
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        string s1, s2;
        cin >> s1 >> s2;
        if (s1 == s2) {
            insert(1, s1, i);
            continue;
        }
        string qwq = get(s1, s2);
        insert(0, qwq, i);
    }
    get_fail();
    for (int i = 1; i <= q; i++) {
        string t1, t2;
        cin >> t1 >> t2;
        if (t1.size() != t2.size()) {
            cout << "0\n";
            continue;
        }
        if (t1 == t2) {
            cout << query(1, t1) << '\n';
            continue; 
        }
        string awa = get(t1, t2);
        cout << query(0, awa) << '\n';
    }
    return 0;
}

::::

3.3 P4052 [JSOI2007] 文本生成器

给定 n 个模式串 s_1\sim s_n，求出长度为 m，且至少包含一个模式串的文本串个数。

1\le n\le 60, 1\le m\le 100, 1\le |s_i|\le 100

考虑正难则反，用所有文本串的个数 26^m，减去不包含模式串的个数。

考虑不包含模式串的文本串个数怎么求。

考虑 AC 自动机。我们观察 AC 自动机的过程，我们是跳 fail 匹配，所以能跳 fail 跳到模式串的节点，显然都不能转移，这个可以在求解 fail 指针求出每个点是否可以转移。

我们在 AC 自动机上 DP，令 dp_{i, j} 表示长度为 i 且结束字符在 AC 自动机上节点为 j 的方案数，转移方程为：

其中 k\in son(j)，vis_u 表示 u 是否会匹配到模式串。

最后答案就是（以下 tot 表示 AC 自动机总点数）：

注意题目中字符集是大写字母，导致我虚空调试半小时

::::success[code]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int mod = 1e4 + 7;
int dp[110][MAXN];
int ch[MAXN][30];
int pos[MAXN];
int fail[MAXN];
int n, m, tot = 1;
string s[MAXN]; 
int cnt[MAXN];
bool vis[MAXN];
void insert(string s, int P) {
    int u = 1;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'A';
        if (ch[u][c] == 0) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    pos[u] = P;
    vis[u] = 1;
}
void get_fail() {
    for (int i = 0; i < 26; i++) ch[0][i] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        vis[u] |= vis[fail[u]];
        q.pop();
        for (int i = 0; i < 26; i++) {
            int v = ch[u][i];
            if (v == 0) {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            fail[v] = ch[fail[u]][i];
            q.push(v);
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        insert(s[i], i);
    }
    get_fail();
    dp[0][1] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= tot; j++)
            if (!vis[j])
                for (int k = 0; k < 26; k++)
                    dp[i][ch[j][k]] = (dp[i][ch[j][k]] + dp[i - 1][j]) % mod;
    int ans = 1;
    for (int i = 1; i <= m; i++) ans = (ans * 26) % mod;
    for (int i = 1; i <= tot; i++)
        if (!vis[i]) ans = (ans - dp[m][i] + mod) % mod;
    cout << ans;
    return 0;
}

::::

3.4 P2292 [HNOI2004] L 语言

一段文章 T 是由若干小写字母构成。一个单词 W 也是由若干小写字母构成。一个字典 D 是若干个单词的集合。我们称一段文章 T 在某个字典 D 下是可以被理解的，是指如果文章 T 可以被分成若干部分，且每一个部分都是字典 D 中的单词。

给定一个字典 D，其中有 n 个单词 s_1\sim s_n，你的程序需要判断 m 个文章 t_1\sim t_m 在字典 D 下是否能够被理解。并给出其在字典 D 下能够被理解的最长前缀的位置。

1 \leq n \leq 20$，$1 \leq m \leq 50$，$1 \leq |s| \leq 20$，$1 \leq |t| \leq 2 \times 10^6

考虑 DP。设 dp_i 表示当前主串 [1, i] 是否可以被拼接，则转移为：

由于 |s| 最多只有 20，所以我们状压保存这最后 20 个状态。

直接转移显然会爆，我们考虑优化。

我们在 AC 自动机上每个状态，维护所有以当前位置结尾的字符串的长度，这个可以通过状压保存，在求 fail 时求出。

求解时，状压维护最后 20 个 DP 信息，第 k 个位置表示当前的 dp_{i - k}，转移则通过判断是否含有对应合法后缀长度且 dp 值为 1 转移，这个可以根据前面处理的信息 O(1) 转移。

::::success[完整代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int ch[MAXN][30];
int pos[MAXN];
int fail[MAXN];
int n, m, tot = 1;
int cnt[MAXN];
int qwq[MAXN];
void insert(string s, int P, int len) {
    int u = 1;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        if (ch[u][c] == 0) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    qwq[u] = (1ll << (len - 1));
    pos[u] = P;
}
void get_fail() {
    for (int i = 0; i < 26; i++) ch[0][i] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        qwq[u] |= qwq[fail[u]];
        for (int i = 0; i < 26; i++) {
            int v = ch[u][i];
            if (v == 0) {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            fail[v] = ch[fail[u]][i];
            q.push(v);
        }
    }
}
void query(string s) {
    int u = 1;
    int mask = 1, ans = 0;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        u = ch[u][c];
        if (mask & qwq[u]) {
            mask = mask << 1ll | 1ll;
            ans = i + 1;
        } else mask <<= 1ll;
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        insert(s, i, s.size()); 
    }
    get_fail();
    for (int i = 1; i <= m; i++) {
        string t;
        cin >> t;
        query(t);
    }
    return 0;
}

::::

3.5 P2414 [NOI2011] 阿狸的打字机

有一个操作序列，有三种操作，且当前有一个字符串：

• 输入一个小写字母，假如在字符串最后。
• 输入一个 B，删除字符串最后一个字符。
• 输入一个 P，打印当前字符串。

把打印的字符串从 1 开始编号，一直到 n。有 m 次询问，每次询问给你两个数 x, y，需要你求出第 x 个打印的字符串在第 y 个打印的字符串中出现了几次。

显然可以通过一个字典树模拟当前的操作序列。

对于询问，我们显然可以使用 AC 自动机每次匹配一遍，但是复杂度显然是错误的。

我们考虑 AC 自动机匹配时实际在干什么：在 Trie 树上 y 的状态中，每个跳 fail 能否跳到 x 结尾。

由于能跳到 x 结尾的一定是 x 结尾的状态在 fail 树中的子树，那么可以将问题转换为：Trie 上 y 结尾到根的状态中，有多少个在 fail 树上 x 结尾的状态的子树中。

由于是子树，我们可以通过 dfs 序转换为序列问题。

大力主席树处理询问即可。

树状数组是什么，离线是什么，阿巴阿巴

::::success[完整代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int ch[MAXN][30];
int pos[MAXN];
int fail[MAXN];
int n, m, tot = 1;
string s, t[MAXN];
vector <int> G[MAXN], g[MAXN];
int siz[MAXN];
int dfn[MAXN], cntt;
int a[MAXN];
int fat[MAXN];
void dfs(int u, int fa) {
    siz[u] = 1;
    dfn[u] = ++cntt;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}
int root[MAXN], cnt;
struct SGT {
    int ls, rs;
    int siz;
} w[MAXN << 2];
void pushup(int u) {
    w[u].siz = w[w[u].ls].siz + w[w[u].rs].siz;
}
void build(int &u, int l, int r) {
    if (!u) u = ++cnt;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(w[u].ls, l, mid);
    build(w[u].rs, mid + 1, r);
}
int update(int u, int l, int r, int p) {
    int x = ++cnt;
    w[x].siz = w[u].siz + 1;
    int mid = (l + r) >> 1;
    if (l == r) return x;
    if (p <= mid) w[x].ls = update(w[u].ls, l, mid, p), w[x].rs = w[u].rs;
    else w[x].rs = update(w[u].rs, mid + 1, r, p), w[x].ls = w[u].ls;
    return x;
}
int query(int u, int l, int r, int L, int R) {
    if (l >= L && r <= R) return w[u].siz;
    int mid = (l + r) >> 1;
    int res = 0;
    if (L <= mid) res += query(w[u].ls, l, mid, L, R);
    if (R > mid) res += query(w[u].rs, mid + 1, r, L, R);
    return res;
}
void dfs1(int u, int fa) {
    root[u] = update(root[fa], 1, cntt, dfn[u]);
    for (auto v : g[u]) dfs1(v, u);
}
int qwq[MAXN], t0t;
void get_fail() {
    for (int i = 0; i < 26; i++) ch[0][i] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        G[fail[u]].push_back(u);
        for (int i = 0; i < 26; i++) {
            int v = ch[u][i];
            if (v == 0) {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            fail[v] = ch[fail[u]][i];
            q.push(v);
        }
    }
    dfs(0, 0);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s;
    cin >> s >> m;
    int n = s.size();
    s = ' ' + s;
    int u = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'B') u = fat[u];
        else if (s[i] == 'P') qwq[++t0t] = u;
        else {
            int c = s[i] - 'a';
            if (!ch[u][c]) ch[u][c] = ++tot, g[u].push_back(ch[u][c]);
            fat[ch[u][c]] = u;
            u = ch[u][c];
        }
    }
    get_fail();
    build(root[0], 1, cntt);
    dfs1(1, 0);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        cout << query(root[qwq[y]], 1, cntt, dfn[qwq[x]], dfn[qwq[x]] + siz[qwq[x]] - 1) << '\n';
    }
    return 0;
}

::::

3.6 P2336 [SCOI2012] 喵星球上的点名

有 n 只喵，每一只有姓和名两个字符串，另外有 m 个点名串。

你需要求出对于每个点名串，有多少只喵的姓或名中包含这个串（每只喵只算一次）；对每只喵，求出其被多少个点名串点过（只要点名串出现在它的姓或名里就算一次）。

喵喵喵

考虑把姓和名合并成一个字符串，在中间加上一个特殊字符，这样只要是点名串的子串，即可匹配成功。

根据上一题的结论，包含一个串的显然是 fail 树上这个串结尾的状态的子树中。

以下中的“树”都是指 fail 树。

首先考虑第一问，对于每个名字串，从尾开始，沿着在字典树的状态往上跳，对于覆盖了这些点的子树，都需要统计。

由于子树的 dfs 序是连续的，所以可以使用树状数组维护每个点被覆盖的次数。

但是我们发现，这样显然会算重。

这里有一个 trick，我们把覆盖到的每个点，按 dfs 序从小到大排序，然后在相邻两个点的 \operatorname{LCA} 处减 1，即可算出正确的覆盖到的点。

::::info[证明] 子树 \text{subtree}(u) 在 DFS 序中对应连续区间 [dfn_u, dfn_u + siz_u - 1]。因此 S 中落入该区间的节点形成连续子序列：

子树内每个节点贡献 + 1，共 r - l + 1 个。相邻 \operatorname{LCA} 的 - 1 贡献中：

• 内部相邻对 (v_l, v_{l + 1}), \dots, (v_{r - 1}, v_r) 共 r - l 个，其 \operatorname{LCA} 均在 \text{subtree}(u) 内；
• 边界相邻对 (v_{l - 1}, v_l) 和 (v_r, v_{r + 1}) 均有一个节点在子树外，其 \operatorname{LCA} 不在 \text{subtree}(u) 内。

因此子树内总和为：

对于第二问，和上面类似，我们对于每个点名串，树状数组加差分求出每个点被覆盖多少次。

然后枚举名字串，看从尾开始，沿着在字典树的状态往上跳，跳到了那些点。然后跳到的点依旧按 dfs 序排序，和上面一样差分，对于相邻两个点，减去 \operatorname{LCA} 的答案。

注意由于字符集太大，不能直接建立字典图，而是直接暴力跳 fail。

::::success[完整代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
map <int, int> ch[MAXN];
int fail[MAXN];
int n, m, tot = 1;
vector <int> G[MAXN];
int siz[MAXN], dfn[MAXN], cntt, dep[MAXN], son[MAXN], top[MAXN], fa[MAXN];
int fat[MAXN];
int Pos1[MAXN], Pos2[MAXN];
int c[MAXN];
int lowbit(int x) { return x & (-x);}
void add(int x, int y) {
    for (int i = x; i <= cntt; i += lowbit(i)) c[i] += y; 
}
int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}
int insert(vector <int> s) {
    int u = 1;
    for (auto c : s) {
        if (ch[u].find(c) == ch[u].end()) ch[u][c] = ++tot, fat[ch[u][c]] = u;
        u = ch[u][c];
    }
    return u;
}
void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    for (auto v : G[u]) {
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}
void dfs2(int u, int Top) {
    top[u] = Top;
    dfn[u] = ++cntt;
    if (son[u]) dfs2(son[u], Top);
    for (auto v : G[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
void get_fail() {
    queue <int> q;
    fail[1] = 0;
    G[0].push_back(1);
    for (auto qwq : ch[1]) {
        int v = qwq.second;
        fail[v] = 1;
        q.push(v);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        G[fail[u]].push_back(u);
        for (auto qwq : ch[u]) {
            int c = qwq.first, v = qwq.second;
            int f = fail[u];
            while (f && f != 1 && ch[f].find(c) == ch[f].end()) f = fail[f];
            if (f && ch[f].find(c) != ch[f].end()) fail[v] = ch[f][c];
            else fail[v] = 1;
            q.push(v);
        }
    }
    dfs1(1, 0);
    dfs2(1, 1);
}
bool cmp(int a, int b) {
    return dfn[a] < dfn[b];
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        vector <int> vec;
        int l;
        cin >> l;
        while (l--) {
            int c;
            cin >> c;
            vec.push_back(c);
        } 
        vec.push_back(10001);
        cin >> l;
        while (l--) {
            int c;
            cin >> c;
            vec.push_back(c);
        } 
        Pos1[i] = insert(vec);
    }
    for (int i = 1; i <= m; i++) {
        vector <int> vec;
        int l;
        cin >> l;
        while (l--) {
            int c;
            cin >> c;
            vec.push_back(c);
        } 
        Pos2[i] = insert(vec);
    }
    get_fail();
    for (int i = 1; i <= n; i++) {
        int u = Pos1[i];
        vector <int> vec;
        while (u) {
            vec.push_back(u);
            add(dfn[u], 1);
            u = fat[u];
        }
        sort(vec.begin(), vec.end(), cmp);
        for (int i = 1; i < vec.size(); i++) add(dfn[lca(vec[i], vec[i - 1])], -1);
    }
    for (int i = 1; i <= m; i++) cout << sum(dfn[Pos2[i]] + siz[Pos2[i]] - 1) - sum(dfn[Pos2[i]] - 1) << '\n';
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= m; i++) {
        add(dfn[Pos2[i]], 1);
        add(dfn[Pos2[i]] + siz[Pos2[i]], -1);
    }
    for (int i = 1; i <= n; i++) {
        int u = Pos1[i];
        vector <int> vec;
        int ans = 0;
        while (u) {
            vec.push_back(u);
            ans += sum(dfn[u]);
            u = fat[u];
        }
        sort(vec.begin(), vec.end(), cmp);
        for (int i = 1; i < vec.size(); i++) ans -= sum(dfn[lca(vec[i], vec[i - 1])]);
        cout << ans << ' ';
    }
    return 0;
}

::::