目录
写在前面
定义
引入
构造
暴力
字典图优化
匹配
在线
离线
复杂度
完整代码
例题
P3796 【模板】AC 自动机（加强版）
P3808 【模板】AC 自动机（简单版）
「JSOI2007」文本生成器
「BJOI2019」奥术神杖
「SDOI2014」数数
「NOI2011」阿狸的打字机
写在最后
写在前面
这篇文章的主体是在没网的悲惨状况下完成的。
前置知识：Trie 树，DFA，KMP 字符串匹配算法。
请务必深刻理解！
定义
\(|\sum|\)：字符集大小，在大多数题目中都等于小写字母个数 26。
\(s[i:j]\)：字符串 \(s\) 的子串 \(s_i\cdots s_j\)。
真前/后缀：字符串 \(s\) 的真前缀定义为满足不等于它本身的 \(s\) 的前缀。同理就有了真后缀的定义：满足不等于它本身的 \(s\) 的后缀。
\(\operatorname{border}\)：字符串 \(s\) 的 \(\operatorname{border}\) 定义为，满足既是 \(s\) 的真前缀，又是 \(s\) 的真后缀的最长的字符串 \(t\)。
如 \(\texttt{aabaa}\) 的 \(\operatorname{border}\) 为 \(\texttt{aa}\)。
引入
P5357 【模板】AC自动机
给定一个文本串 \(s\)，\(n\) 个模式串 \(t_1\sim t_n\)，求在文本串中各模式串分别出现的次数。
字符串仅由小写字母构成。可能出现重复的模式串。
\(1\le n\le 2\times 10^5\)，\(\sum |t_i|\le 2\times 10^5\)，\(1\le |s|\le 2\times 10^6\)。
若 \(n = 1\)，可以使用 KMP 算法在 \(O(|s| + |t|)\) 的时空复杂度内求解。
AC 自动机可以认为是 KMP 算法在 Trie 树上的应用，与 KMP 算法在失配时应用已匹配部分的 \(\operatorname{border}\) 进行跳转类似，AC 自动机在失配时会根据失配指针跳转到 Trie 树上代表已匹配部分的 \(\operatorname{border}\) 的节点，从而加速匹配。
值得注意的是，KMP 也是一种建立在模式串上的自动机。AC 自动机与 KMP 的关系，相当于 SAM 与 广义 SAM 的关系。
构造
先把所有字符串插入 Trie 中。可能存在相同模式串，需要记录每个状态代表的字符串的编号，可使用 vector 实现。之后再考虑如何建立 ACAM。
void Insert(int id_, char *s_) {
int now = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[now][s_[i] - 'a']) tr[now][s_[i] - 'a'] = ++ node_num;
now = tr[now][s_[i] - 'a'];
}
id[now].push_back(id_); //记录
}
暴力
按照 KMP 的思路直接构造。
与 KMP 类似地，记 \(\operatorname{fail}_u\) 表示从根节点到状态 \(u\) 所代表的字符串（即已匹配部分）的 \(\operatorname{border}\) 对应的字符串的状态。
在更新 \(\operatorname{fail}_u\) 前，必须保证比 \(u\) 深度浅的节点都已被更新过。则需要按照 bfs 的顺序进行构造。
考虑使用 \(u\) 来更新 \(v=\operatorname{tr}(u,c)\) 的信息，其中 \(c\) 是 Trie 树转移边上的字符，\(\operatorname{tr}(u,c)\) 表示在 \(u\) 按照转移边 \(c\) 转移到的状态。注意此处 \(\operatorname{tr}(u,c)\) 可以不存在。
同 KMP，考察 \(\operatorname{tr}(\operatorname{fail}_u, c)\) 的存在性。若存在，则 \(\operatorname{fail}_{\operatorname{tr}(u,c)} = \operatorname{tr}({\operatorname{fail}_u, c})\)。若不存在则继续考察 \(\operatorname{tr}(\operatorname{fail}_{\operatorname{fail}_u})\dots\)，直到找到满足条件的状态，或者到达根节点。
代码如下：
void Build() {
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
int v_ = tr[u_][i], j = fail[u_];
while (j && !tr[j][i]) j = fail[j]; //大力跳 fail
if (tr[j][i]) j = tr[j][i]; //有出边
fail[v_] = j;
if (v_) q.push(v_);
}
}
}
字典图优化
可以发现，在暴力的 while 跳 \(\operatorname{fail}\) 中，可能会出现重复的跳跃，这是暴力构建复杂度较高的主要原因。
考虑将重复的跳跃进行路径压缩，可以写出如下的代码：
void Build() {
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
if (tr[u_][i]) {
fail[tr[u_][i]] = tr[fail[u_]][i];
q.push(tr[u_][i]);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
稍微解释一下。在暴力的代码中，跳 \(\operatorname{fail}\) 是这样的：while (j && !tr[j][i]) j = fail[j];。
而在优化后的代码中，\(\operatorname{fail}_u\) 已经指向了在未优化代码中 \(j\) 最后的位置，因此可以直接赋值 fail[tr[u_][i]] = tr[fail[u_]][i];。实现这一功能的关键是这一句：tr[u_][i] = tr[fail[u_]][i];。
关于其原理，可以考虑在暴力中什么情况下会多次跳 \(\operatorname{fail}\)。
显然，当 while 中出现 \(\operatorname{tr}(\operatorname{fail}_u, i)\) 不存在的情况时，才会继续考察 \(\operatorname{tr}(\operatorname{fail}_{\operatorname{fail}_u}, i)\) 的存在性。但在优化后，通过 tr[u_][i] = tr[fail[u_]][i]; 的赋值后，会让本不存在的 \(\operatorname{tr}(\operatorname{fail}_u,i)\) 变为 \(\operatorname{tr}(\operatorname{fail}_{\operatorname{fail}_u}, i)\)，成为一个“存在”的状态。通过这种类似递推的定义，从而完成了路径压缩的过程。
记 Trie 的节点个数为 \(n\)，优化后构建 ACAM 的时间复杂度显然为 \(O(n|\sum|)\)。
匹配
在线
把文本串扔到 ACAM 上进行匹配。经过上述的路径压缩，若当前所在的状态 \(u\) 不存在 \(s_i\) 的转移，不需要大力跳 \(\operatorname{fail}\)，可以直接转移到 \(tr(u:s_i)\)。
设当前匹配到 \(s_i\)，匹配到状态 \(u\)。可以发现，此时的已匹配部分（根到 \(u\) 的路径）是 \(s[1,i]\) 的一段后缀，也是某模式串的一段前缀。
跳 \(\operatorname{fail}\) 可以认为是在削除已匹配的前缀。在匹配过程中，每跑到一个状态，就暴力地跳 \(\operatorname{fail}\)，即可枚举出所有被已匹配部分包含的模式串的前缀。
可以在线地统计信息。
void Query(char *s_) {
int now = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
now = tr[now][s_[i] - 'a'];
for (int j = now; j; j = fail[j]) { //枚举已匹配部分包含的模式串
for (int k = 0, lim = id[j].size(); k < lim; ++ k) { //累计答案
sum[id[j][k]] ++;
}
}
}
for (int i = 1; i <= n; ++ i) printf("%d\n", sum[i]);
}
离线
可以发现上述在线统计贡献时只能每次令贡献 \(+1\)，算法复杂度上界显然为 \(O(n|t|)\)。
在 P3808 【模板】AC 自动机（简单版） 和 P3796 【模板】AC自动机（加强版） 大多数人都采用了这种写法。然而在 引入 中这种写法会被卡到 60。
于是考虑离线操作，标记匹配状态，再离线地统计贡献。
对于引入中给出的问题，先把文本串 \(t\) 放到 ACAM 上跑一遍，记录遍历到了哪些状态，并使改状态出现次数 \(+1\)。枚举到 \(t_i\) 时的状态 \(now\) 代表了一个作为 \(t[1:i]\) 的后缀的最长的某模式串的前缀。
之后建立 \(\operatorname{fail}\) 树，在 \(\operatorname{fail}\) 树上 DP。根据 \(\operatorname{fail}\) 的定义和它们的相互包含关系，即可求得每个状态在文本串中出现的次数 \(\operatorname{size}\)，从而得到模式串的出现次数 \(\operatorname{sum}\)。
上述做法类似树上差分，记 Trie 的节点个数为 \(n\)，显然总时间复杂度 \(O(|t| + n)\) 级别。
void Dfs(int u_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
Dfs(v_);
size[u_] += size[v_]; //u_ 被 v_ 包含
}
for (int i = 0, lim = id[u_].size(); i < lim; ++ i) { //枚举状态代表的模式串
sum[id[u_][i]] = size[u_];
}
}
void Query(char *t_) {
int now = 0, lth = strlen(t_ + 1);
for (int i = 1; i <= lth; ++ i) {
now = tr[now][t_[i] - 'a'];
++ size[now];
}
for (int i = 1; i <= node_num; ++ i) Add(fail[i], i);
Dfs(0);
for (int i = 1; i <= n; ++ i) printf("%d\n", sum[i]);
}
复杂度
记 Trie 的节点数量为 \(n\)，\(n\) 的上界为 \(\sum |s_i|\)。
对于时间复杂度，构建 Trie 图的复杂度为 \(O(n|\sum|)\)，匹配的复杂度为 \(O(|t| + n)\) 级别。
对于空间复杂度，显然复杂度为 \(O(n|\sum|)\)。
完整代码
//知识点：ACAM
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define LL long long
const int kT = 2e6 + 10;
const int kN = 2e5 + 10;
//=============================================================
int n;
char s[kT];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
namespace ACAM {
std::vector <int> id[kN];
int node_num, tr[kN][26], sum[kN], fail[kN];
int e_num, size[kN], head[kN], v[kN], ne[kN];
void Add(int u_, int v_) {
v[++ e_num] = v_;
ne[e_num] = head[u_];
head[u_] = e_num;
}
void Dfs(int u_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
Dfs(v_);
size[u_] += size[v_];
}
for (int i = 0, lim = id[u_].size(); i < lim; ++ i) {
sum[id[u_][i]] = size[u_];
}
}
void Insert(int id_, char *s_) {
int now = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[now][s_[i] - 'a']) tr[now][s_[i] - 'a'] = ++ node_num;
now = tr[now][s_[i] - 'a'];
}
id[now].push_back(id_);
}
void Build() {
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
if (tr[u_][i]) {
fail[tr[u_][i]] = tr[fail[u_]][i];
q.push(tr[u_][i]);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
void Query(char *t_) {
int now = 0, lth = strlen(t_ + 1);
for (int i = 1; i <= lth; ++ i) {
now = tr[now][t_[i] - 'a'];
++ size[now];
}
for (int i = 1; i <= node_num; ++ i) Add(fail[i], i);
Dfs(0);
for (int i = 1; i <= n; ++ i) printf("%d\n", sum[i]);
}
}
//=============================================================
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s + 1);
ACAM::Insert(i, s);
}
ACAM::Build();
scanf("%s", s + 1);
ACAM::Query(s);
return 0;
}
例题
P3796 【模板】AC 自动机（加强版）
\(t\) 组数据，每次给定一个文本串 \(s\)，\(n\) 个模式串 \(t_1\sim t_n\)，求在文本串中出现次数最多的模式串。
字符串仅由小写字母构成。模式串互不相同。
\(1\le t\le 50\)，\(1\le n\le 150\)，\(1\le |t_i|\le 70\)，\(1\le |s|\le 10^6\)。
板子。
//知识点：ACAM
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
const int kN = 150 + 5;
const int kT = 1e6 + 10;
const int kNN = 2e5 + 10;
//=============================================================
int n;
char s[kN][71], t[kT];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
struct ACAM {
int node_num, tr[kNN][26], id[kNN], size[kNN], sum[kNN], fail[kNN];
int e_num, head[kNN], v[kNN], ne[kNN];
void Init() {
node_num = e_num = 0;
memset(tr, 0, sizeof (tr));
memset(id, 0, sizeof (id));
memset(size, 0, sizeof (size));
memset(head, 0, sizeof (head));
memset(fail, 0, sizeof (fail));
}
void Add(int u_, int v_) {
v[++ e_num] = v_;
ne[e_num] = head[u_];
head[u_] = e_num;
}
void Dfs(int u_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
Dfs(v_);
size[u_] += size[v_];
}
sum[id[u_]] = size[u_];
}
void Insert(int id_, char *s_) {
int now = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[now][s_[i] - 'a']) tr[now][s_[i] - 'a'] = ++ node_num;
now = tr[now][s_[i] - 'a'];
}
id[now] = id_;
}
void Build() {
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
if (tr[u_][i]) {
fail[tr[u_][i]] = tr[fail[u_]][i];
q.push(tr[u_][i]);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
void Query(char *s_) {
int now = 0, ans = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
now = tr[now][s_[i] - 'a'];
++ size[now];
}
for (int i = 1; i <= node_num; ++ i) Add(fail[i], i);
Dfs(0);
for (int i = 1; i <= n; ++ i) Chkmax(ans, sum[i]);
printf("%d\n", ans);
for (int i = 1; i <= n; ++ i) {
if (sum[i] == ans) printf("%s\n", s[i] + 1);
}
}
} acam;
//=============================================================
int main() {
while (true) {
n = read();
if (! n) break;
acam.Init();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s[i] + 1);
acam.Insert(i, s[i]);
}
acam.Build();
scanf("%s", t + 1);
acam.Query(t);
}
return 0;
}
P3808 【模板】AC 自动机（简单版）
给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\)，求有多少个不同的模式串在文本串里出现过。
字符串仅由小写字母构成。两个模式串不同当且仅当他们编号不同。
\(1\le n,\sum|s_i|\le 10^6\)，\(1\le |t|\le 10^6\)。
1S，512MB。
题意考虑模式串是否出现，在 Trie 中仅需维护每个状态代表多少个模式串，记为 \(\operatorname{cnt}\)。
建出 ACAM，文本串匹配过程中记录到达过哪些状态。之后在 \(\operatorname{fail}\) 树上 DP，求得哪些状态在文本串中出现过。将它们的 \(\operatorname{cnt}\) 求和即可。
总时空复杂度 \(O(\sum |s_i|)\) 级别。
//知识点：ACAM
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n;
char s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
namespace ACAM {
int node_num, tr[kN][26], cnt[kN], fail[kN];
int e_num, head[kN], v[kN], ne[kN];
bool size[kN];
void Add(int u_, int v_) {
v[++ e_num] = v_;
ne[e_num] = head[u_];
head[u_] = e_num;
}
int Dfs(int u_) {
int ret = 0;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
ret += Dfs(v_);
size[u_] |= size[v_];
}
return ret + size[u_] * cnt[u_];
}
void Insert(int id_, char *s_) {
int now = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[now][s_[i] - 'a']) tr[now][s_[i] - 'a'] = ++ node_num;
now = tr[now][s_[i] - 'a'];
}
++ cnt[now];
}
void Build() {
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
if (tr[u_][i]) {
fail[tr[u_][i]] = tr[fail[u_]][i];
q.push(tr[u_][i]);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
void Query(char *s_) {
int now = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
now = tr[now][s_[i] - 'a'];
size[now] = 1;
}
for (int i = 1; i <= node_num; ++ i) Add(fail[i], i);
printf("%d\n", Dfs(0));
}
}
//=============================================================
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s + 1);
ACAM::Insert(i, s);
}
ACAM::Build();
scanf("%s", s + 1);
ACAM::Query(s);
return 0;
}
「JSOI2007」文本生成器
给定 \(n\) 个只由大写字母构成的模式串 \(s_1\sim s_n\)，给定参数 \(m\)。
求有多少个长度为 \(m\) 的只由大写字母构成的字符串，满足其中至少有一个给定的模式串，答案对 \(10^4 + 7\) 取模。
\(1\le n\le 60\)，\(1\le |s_i|,m\le 100\)。
1S，128MB。
？这做法是个套路
先建立 ACAM，建 Trie 图的时候顺便标记所有包含模式串的状态。记这些状态构成集合 \(\mathbf{S}\)。
发现不好处理含有多个模式串的情况，考虑补集转化，答案为所有串的个数 \(26^{m}\) 减去不含模式串的串个数。
考虑 ACAM 上 DP。设 \(f_{i,j}\) 表示长度为 \(i\)，在 ACAM 上匹配的结束状态为 \(j\)，不含模式串的字符串的个数。
初始化空串 \(f_{0,0} = 1\)。转移时枚举串长，状态，转移函数，避免转移到包含模式串的状态，有：
\[f_{i,j} = \begin{cases}
&\sum\limits_{\operatorname{trans}(u, k) = j} f_{i-1, u} &(j\notin \mathbf{S})\\
&0 &(j\in \mathbf{S})
\end{cases}\]
注意转移时需要枚举空串的状态 0。实现时滚动数组 + 填表即可。
记 Trie 的大小为 \(|T|\)，答案即为：
\[26^m - \sum_{i=0}^{|T|} f_{m,i} \pmod{10^4+7}
\]
总时间复杂度 \(O(m|T||\sum|)\) 级别。
为什么可以这样转移？
可以发现建立 Trie 图后，这个转移过程就相当于字符串的匹配过程。
可以认为 DP 过程是通过所有长度为 \(i-1\) 的字符串在 ACAM 上做匹配，从而得到长度为 \(i\) 的字符串对应的状态。
//知识点：ACAM
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
const int kN = 100 + 10;
const int mod = 1e4 + 7;
//=============================================================
int n, m, ans;
char s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) {
w = (w << 3) + (w << 1) + (ch ^ '0');
}
return f * w;
}
void Chkmax(int &fir_, int sec_) {
if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
if (sec_ < fir_) fir_ = sec_;
}
namespace ACAM {
int node_num, tr[60 * kN][26], fail[60 * kN], f[2][60 * kN];
bool tag[60 * kN];
void Insert(char *s_) {
int u_ = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[u_][s_[i] - 'A']) tr[u_][s_[i] - 'A'] = ++ node_num;
u_ = tr[u_][s_[i] - 'A'];
}
tag[u_] = true;
}
void Build() {
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
int v_ = tr[u_][i];
if (v_) {
fail[v_] = tr[fail[u_]][i];
tag[v_] |= tag[fail[v_]];
q.push(v_);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
void Query() {
ans = f[0][0] = 1;
for (int i = 1; i <= m; ++ i) ans = 26ll * ans % mod;
for (int i = 1, now = 1; i <= m; ++ i, now ^= 1) {
memset(f[now], 0, sizeof (f[now])); //caution：reset
for (int j = 0; j <= node_num; ++ j) {
for (int k = 0; k < 26; ++ k) {
if (tag[tr[j][k]]) continue;
f[now][tr[j][k]] += f[now ^ 1][j];
f[now][tr[j][k]] %= mod;
}
}
}
for (int i = 0; i <= node_num; ++ i) {
ans = (ans - f[m % 2][i] + mod) % mod;
}
}
}
//=============================================================
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s + 1);
ACAM::Insert(s);
}
ACAM::Build();
ACAM::Query();
printf("%d\n", ans);
return 0;
}
「BJOI2019」奥术神杖
给定一只由数字和\(\texttt{.}\)构成的字符串 \(s\)。给定 \(m\) 个特殊串 \(t_{1}\sim t_{m}\)，\(t_i\) 的权值为 \(v_i\)。
需要在 \(s\) 中为\(\texttt{.}\)的位置上填入数字，一种填入方案的价值定义为：
\[\sqrt[c]{\prod_{i=1}^{c} w_i}
\]其中 \(w\) 表示在该填入方案中，出现过的特殊串的价值的可重集合，其大小为 \(c\)。
每个位置填入的数字任意，最大化填入方案的价值，并输出任意一个方案。
\(1\le m,|s|,\sum|t_i|\le 1501\)，\(1\le v_i\le 10^9\)。
1S，512MB。
对于两种填入方案，我们只关心它们价值的相对大小。带着根号不易比较大小，套路地取个对数，之后化下式子：
\[\begin{aligned}
\large \log {\sqrt[c]{\prod_{i=1}^{c} w_i}} =& \dfrac{\log {\left(\prod\limits_{i=1}^{c} w_i\right)}}{c}\\
=& \dfrac{\sum\limits_{i=1}^{c} \log {w_i}}{c}
\end{aligned}\]
这是一个显然的 01 分数规划的形态，考虑二分答案。存在一种填入方案价值不小于 \(mid\) 的充要条件为：
\[\begin{aligned}
\dfrac{\sum\limits_{i=1}^{c} \log {w_i}}{c}\ge mid \iff \sum\limits_{i=1}^{c}\left(\log {w_i} - mid\right)\ge 0
\end{aligned}\]
考虑 DP 检查二分量 \(mid\) 是否合法。
具体地，先将特殊串 \(t_i\) 的权值设为 \(\log v_i - mid\)，更新 ACAM 上各状态的权值，之后在 ACAM 上模拟匹配过程套路 DP。
设 \(f_{i,j}\) 表示长度为 \(i\)，在 ACAM 上匹配的结束状态为 \(j\) 的串的最大价值。
初始化 \(f_{0,0} = 0\)，转移时枚举串长，状态，转移函数。注意某一位不为\(\texttt{.}\)时转移函数只能为串中的字符，则有：
\[f_{i,j} = \begin{cases}
&\max\limits_{\operatorname{trans}(u, s_i) = j} f_{i-1, u} + \operatorname{val}_{j} &(s_i\not= \texttt{.})\\
&\max\limits_{\operatorname{trans}(u, k) = j} f_{i-1, u} + \operatorname{val}_{j} &(s_i= \texttt{.})
\end{cases}\]
注意记录转移时的前驱与转移函数，根据前驱还原出方案即可。
总复杂度 \(O(\left(10|s|\cdot\sum |t_i|\right)\log w)\) 级别，\(\log w\) 为二分次数。
//知识点：ACAM，分数规划
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
#define DB double
const int kN = 3e3 + 10;
const DB kInf = 1e10;
const DB eps = 1e-6;
//=============================================================
int n, m;
char origin[kN], s[kN], ans[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
namespace ACAM {
int node_num = 0, tr[kN][10], fail[kN], cnt[kN], from[kN][kN];
DB sum[kN], val[kN], f[kN][kN];
char ch[kN][kN];
void Insert(char *s_, int val_) {
int u_ = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[u_][s_[i] - '0']) tr[u_][s_[i] - '0'] = ++ node_num;
u_ = tr[u_][s_[i] - '0'];
}
sum[u_] += log(val_);
cnt[u_] ++;
}
void Build() {
std::queue <int> q;
for (int i = 0; i < 10; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int u_ = q.front(); q.pop();
for (int i = 0; i < 10; ++ i) {
int v_ = tr[u_][i];
if (v_) {
fail[v_] = tr[fail[u_]][i];
sum[v_] += sum[fail[v_]];
cnt[v_] += cnt[fail[v_]];
q.push(v_);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
bool DP(DB mid_) {
//初始化
for (int i = 0; i <= node_num; ++ i) val[i] = sum[i] - cnt[i] * mid_;
for (int i = 0; i <= n; ++ i) {
for (int j = 0; j <= node_num; ++ j) {
f[i][j] = -kInf;
}
}
f[0][0] = 0;
//DP
for (int i = 0; i < n; ++ i) {
for (int j = 0; j <= node_num; ++ j) {
if (f[i][j] == -kInf) continue;
if (origin[i + 1] == '.') {
for (int k = 0; k < 10; ++ k) {
int v_ = tr[j][k];
if (f[i + 1][v_] < f[i][j] + val[v_]) {
f[i + 1][v_] = f[i][j] + val[v_];
from[i + 1][v_] = j;
ch[i + 1][v_] = k + '0';
}
}
} else {
int v_ = tr[j][origin[i + 1] - '0'];
if (f[i + 1][v_] < f[i][j] + val[v_]) {
f[i + 1][v_] = f[i][j] + val[v_];
from[i + 1][v_] = j;
ch[i + 1][v_] = origin[i + 1];
}
}
}
}
//寻找最优解
int pos = 0;
for (int i = 0; i <= node_num; ++ i) {
if (f[n][i] > f[n][pos]) pos = i;
}
if (f[n][pos] <= 0) return false;
for (int i = n, j = pos; i; -- i) {
ans[i] = ch[i][j];
j = from[i][j];
}
return true;
}
}
//=============================================================
int main() {
n = read(), m = read();
scanf("%s", origin + 1);
for (int i = 1; i <= m; ++ i) {
scanf("%s", s + 1);
int val = read();
ACAM::Insert(s, val);
}
ACAM::Build();
for (DB l = 0, r = log(kInf); r - l >= eps; ) {
DB mid = (l + r) / 2.0;
if (ACAM::DP(mid)) {
l = mid;
} else {
r = mid;
}
}
printf("%s", ans + 1);
return 0;
}
「SDOI2014」数数
给定一个整数 \(n\)，一大小为 \(m\) 的数字串集合 \(s\)。
求不以 \(s\) 中任意一个数字串作为子串的，不大于 \(n\) 的数字的个数。
\(1\le n\le 10^{1201}\)，\(1\le m\le 100\)，\(1\le \sum |s_i|\le 1500\)。\(n\) 没有前导零，\(s_i\) 可能存在前导零。
1S，128MB。
数位 DP 相关内容可以阅读：「笔记」数位DP。
题目要求不以 \(s\) 中任意一个数字串作为子串，想到这题：「JSOI2007」文本生成器。首先套路地对给定集合的串构建 ACAM，并在 ACAM 上标记所有包含集合内的子串的状态。
之后考虑在 ACAM 上模拟串匹配的过程做数位 DP。发现前缀所在状态储存了前缀的所有信息，可以将其作为 dfs 的参数。
设 Dfs(int now_, int pos_, bool zero_, bool lim_) { 表示前缀匹配到的 ACAM 的状态为 \(\operatorname{pos}\) 时，合法的数字的数量。转移时沿 ACAM 上的转移函数转移，避免转移到被标记的状态。再简单记忆化即可。
存在 \(\operatorname{trans}(0, 0) = 0\)，这样直接 dfs 也能顺便处理不同长度的数字串。
总复杂度 \(O(\log_{10}(n)\sum |s_i|)\) 级别。
//知识点：ACAM，数位 DP
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
const int kN = 1500 + 10;
const int mod = 1e9 + 7;
//=============================================================
int n, m, ans;
char num[kN], s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
namespace ACAM {
const int kSigma = 10;
int node_num, tr[kN][kSigma], last[kN], fail[kN];
int f[kN][kN];
bool tag[kN];
void Insert(char *s_) {
int u_ = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[u_][s_[i] - '0']) tr[u_][s_[i] - '0'] = ++ node_num;
u_ = tr[u_][s_[i] - '0'];
last[u_] = s_[i] - '0';
}
tag[u_] = true;
}
void Build() {
std:: queue <int> q;
for (int i = 0; i < kSigma; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (!q.empty()) {
int u_ = q.front(); q.pop();
tag[u_] |= tag[fail[u_]];
for (int i = 0; i < kSigma; ++ i) {
int v_ = tr[u_][i];
if (v_) {
fail[v_] = tr[fail[u_]][i];
q.push(v_);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
int Dfs(int now_, int pos_, bool zero_, bool lim_) {
if (now_ > n) return 1;
if (!zero_ && !lim_ && f[now_][pos_] != -1) return f[now_][pos_];
int ret = 0;
for (int i = 0, up = lim_ ? num[now_] - '0': 9; i <= up; ++ i) {
int v_ = tr[pos_][i];
if (tag[v_]) continue;
if (zero_ && !i) ret += Dfs(now_ + 1, 0, true, lim_ && i == num[now_] - '0');
else ret += Dfs(now_ + 1, v_, false, lim_ && i == num[now_] - '0');
ret %= mod;
}
if (!zero_ && !lim_) f[now_][pos_] = ret;
return ret;
}
int DP() {
memset(f, -1, sizeof (f));
return Dfs(1, 0, true, true);
}
}
//=============================================================
int main() {
scanf("%s", num + 1);
n = strlen(num + 1);
m = read();
for (int i = 1; i <= m; ++ i) {
scanf("%s", s + 1);
ACAM::Insert(s);
}
ACAM::Build();
printf("%d\n", ACAM::DP());
return 0;
}
「NOI2011」阿狸的打字机
建议先阅读原题面后再阅读简述题面。
通过奇怪的方法给定 \(n\) 个字符串 \(s_1\sim s_n\)，给定 \(m\) 次询问。
每次询问给定参数 \(x\)，\(y\)，求在字符串 \(s_y\) 中 \(s_x\) 的出现次数。
\(1\le n,m,|\sum s_i|\le 10^5\)。
1S，256MB。
首先可以发现，题中给出的打字的过程与 Trie 的插入过程类似，由此可以直接构建出所有串的 Trie。
对 Trie 建立 ACAM 后，先考虑如何暴力查询。
对于每一次询问，都将字符串 \(s_y\) 扔到 ACAM 上匹配。每匹配到一个状态，就暴力上跳考察其在 \(\operatorname{fail}\) 树上的祖先中是否包含 \(s_x\) 对应状态。若包含则证明 \(s_x\) 作为当前匹配部分的一个后缀出现了，贡献累计即为答案。
总复杂度可以达到 \(O(T|\sum| + m|s_i|)\) 级别。其中 \(T\) 为 ACAM 节点数量，其上限为 \(\sum |s_i|\)。
注意到每次匹配的文本串都是模式串，这说明在匹配过程中，不会出现失配情况，且各状态不重复。即匹配过程中经过的路径是 Trie 中的一条自根向下的链。
观察暴力的过程，询问 \((x,y)\) 的答案即为祖先包括 \(s_x\) 状态的 \(s_y\) 的状态数。
由上述性质，这也可以理解为 \(\operatorname{fail}\) 树上祖先包括 \(s_x\) 的，自根至 \(s_y\) 的 Trie 上的链上的节点数量。
更具体地，考虑建立 \(\operatorname{fail}\) 树，答案为 \(s_x\) \(\operatorname{fail}\) 的子树中自根到 \(s_y\) 对应状态的链上的节点数量。
如何实现？对于询问 \((x,y)\)，考虑大力标记 \(s_y\) 对应的所有状态，再查询 \(\operatorname{fail}\) 树上 \(s_x\) 的子树中被标记点数。上述过程可通过 dfn 序 + 树状数组完成。
如果对每次询问都做一次上面的过程，显然是非常浪费的。考虑离线所有询问，在每次询问的状态 \(s_y\) 上打一个询问 \(s_x\) 的标记。
之后在 Trie 上 dfs，每第一次访问到一个节点，就令树状数组中对应 dfn 位置 \(+1\)，表示标记该节点。从该节点回溯时再 \(-1\)。
可以发现，dfs 到状态 \(u\) 时，被标记的节点恰好组成了自根至 \(s_y\) 的 Trie 上的链上的节点。则访问到 \(u\) 即可直接查询离线下来的询问。
总时间负责度 \(O(T|\sum| + m\log T)\)，其中 \(T\) 为 ACAM 节点数量，其上限为 \(\sum |s_i|\)。
实现细节详见代码，注意映射关系。
//知识点：ACAM，BIT
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, ans[kN], pos[kN];
char s[kN];
std::vector <int> query1[kN], query2[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
namespace BIT {
#define low(x) (x&-x)
int Lim, t[kN];
void Init(int lim_) {
Lim = lim_;
}
void Insert(int pos_, int val_) {
for (int i = pos_; i <= Lim; i += low(i)) {
t[i] += val_;
}
}
int Sum(int pos_) {
int ret = 0;
for (int i = pos_; i; i -= low(i)) {
ret += t[i];
}
return ret;
}
int Query(int l_, int r_) {
return Sum(r_) - Sum(l_ - 1);
}
#undef low
}
namespace ACAM {
int node_num, fa[kN], tr[kN][26], fail[kN];
int e_num, head[kN], v[kN], ne[kN];
int dfn_num, dfn[kN], size[kN];
std::vector <int> trans[kN]; //原 Trie 树上的转移。因为建立了 Trie 图，需要把它记录下来，
void Read(char *s_) { //按照读入建立 Trie
int now = 0;
for(int i = 1, lim = strlen(s_ + 1); i <= lim; ++ i) {
if (s_[i] == 'P') {
pos[++ n] = now;
} else if (s_[i] == 'B') {
now = fa[now];
} else {
if (!tr[now][s_[i] - 'a']) {
tr[now][s_[i] - 'a'] = ++ node_num;
trans[now].push_back(node_num);
fa[node_num] = now;
}
now = tr[now][s_[i] - 'a'];
}
}
}
void Add(int u_, int v_) {
v[++ e_num] = v_;
ne[e_num] = head[u_];
head[u_] = e_num;
}
void Dfs(int u_) {
dfn[u_] = ++ dfn_num;
size[u_] = 1;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
Dfs(v_);
size[u_] += size[v_];
}
}
void Build(char *s_) {
Read(s_);
std::queue <int> q;
for (int i = 0; i < 26; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (! q.empty()) {
int now = q.front(); q.pop();
for (int i = 0; i < 26; ++ i) {
if (tr[now][i]) {
fail[tr[now][i]] = tr[fail[now]][i];
q.push(tr[now][i]);
} else {
tr[now][i] = tr[fail[now]][i];
}
}
}
for (int i = 1; i <= node_num; ++ i) Add(fail[i], i);
Dfs(0);
BIT::Init(node_num + 1);
}
void Query(int u_) { //dfs 回答询问到 u_
BIT::Insert(dfn[u_], 1); //标记
for (int i = 0, lim = query1[u_].size(); i < lim; ++ i) { //枚举此时可以回答的询问
int x = query1[u_][i], id = query2[u_][i]; //查询 x 的子树中标记点的个数
ans[id] = BIT::Query(dfn[x], dfn[x] + size[x] - 1);
}
for (int i = 0, lim = trans[u_].size(); i < lim; ++ i) Query(trans[u_][i]);
BIT::Insert(dfn[u_], -1); //去除标记
}
}
//=============================================================
int main() {
scanf("%s", s + 1);
ACAM::Build(s);
int m = read();
for (int i = 1; i <= m; ++ i) { //离线询问
int x = read(), y = read();
query1[pos[y]].push_back(pos[x]);
query2[pos[y]].push_back(i);
}
ACAM::Query(0);
for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
return 0;
}
写在最后
参考资料：
AC 自动机 - OI Wiki
AC自动机学习笔记 - ouuan的博客
