写在前面
这篇文章的主体是在没网的悲惨状况下完成的。
前置知识：Trie 树，DFA，KMP 字符串匹配算法。
请务必深刻理解！
定义
(|sum|)：字符集大小，在大多数题目中都等于小写字母个数 26。
(s[i:j])：字符串 (s) 的子串 (s_icdots s_j)。
真前/后缀：字符串 (s) 的真前缀定义为满足不等于它本身的 (s) 的前缀。同理就有了真后缀的定义：满足不等于它本身的 (s) 的后缀。
(operatorname{border})：字符串 (s) 的 (operatorname{border}) 定义为，满足既是 (s) 的真前缀，又是 (s) 的真后缀的最长的字符串 (t)。
如 ( exttt{aabaa}) 的 (operatorname{border}) 为 ( exttt{aa})。
引入
给定一个文本串 (s)，(n) 个模式串 (t_1sim t_n)，求在文本串中各模式串分别出现的次数。
字符串仅由小写字母构成。可能出现重复的模式串。
(1le nle 2 imes 10^5)，(sum |t_i|le 2 imes 10^5)，(1le |s|le 2 imes 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
", 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
", 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
", 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_1sim t_n)，求在文本串中出现次数最多的模式串。
字符串仅由小写字母构成。模式串互不相同。
(1le tle 50)，(1le nle 150)，(1le |t_i|le 70)，(1le |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
", ans);
for (int i = 1; i <= n; ++ i) {
if (sum[i] == ans) printf("%s
", 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)，求有多少个不同的模式串在文本串里出现过。
字符串仅由小写字母构成。两个模式串不同当且仅当他们编号不同。
(1le n,sum|s_i|le 10^6)，(1le |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
", 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_1sim s_n)，给定参数 (m)。
求有多少个长度为 (m) 的只由大写字母构成的字符串，满足其中至少有一个给定的模式串，答案对 (10^4 + 7) 取模。
(1le nle 60)，(1le |s_i|,mle 100)。
1S，128MB。
？这做法是个套路
先建立 ACAM，建 Trie 图的时候顺便标记所有包含模式串的状态。记这些状态构成集合 (mathbf{S})。
发现不好处理含有多个模式串的情况，考虑补集转化，答案为所有串的个数 (26^{m}) 减去不含模式串的串个数。
考虑 ACAM 上 DP。设 (f_{i,j}) 表示长度为 (i)，在 ACAM 上匹配的结束状态为 (j)，不含模式串的字符串的个数。
初始化空串 (f_{0,0} = 1)。转移时枚举串长，状态，转移函数，避免转移到包含模式串的状态，有：
注意转移时需要枚举空串的状态 0。实现时滚动数组 + 填表即可。
记 Trie 的大小为 (|T|)，答案即为：
总时间复杂度 (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
", ans);
return 0;
}
「BJOI2019」奥术神杖
给定一只由数字和( exttt{.})构成的字符串 (s)。给定 (m) 个特殊串 (t_{1}sim t_{m})，(t_i) 的权值为 (v_i)。
需要在 (s) 中为( exttt{.})的位置上填入数字，一种填入方案的价值定义为：[sqrt[c]{prod_{i=1}^{c} w_i} ]其中 (w) 表示在该填入方案中，出现过的特殊串的价值的可重集合，其大小为 (c)。
每个位置填入的数字任意，最大化填入方案的价值，并输出任意一个方案。
(1le m,|s|,sum|t_i|le 1501)，(1le v_ile 10^9)。
1S，512MB。
对于两种填入方案，我们只关心它们价值的相对大小。带着根号不易比较大小，套路地取个对数，之后化下式子：
这是一个显然的 01 分数规划的形态，考虑二分答案。存在一种填入方案价值不小于 (mid) 的充要条件为：
考虑 DP 检查二分量 (mid) 是否合法。
具体地，先将特殊串 (t_i) 的权值设为 (log v_i - mid)，更新 ACAM 上各状态的权值，之后在 ACAM 上模拟匹配过程套路 DP。
设 (f_{i,j}) 表示长度为 (i)，在 ACAM 上匹配的结束状态为 (j) 的串的最大价值。
初始化 (f_{0,0} = 0)，转移时枚举串长，状态，转移函数。注意某一位不为( exttt{.})时转移函数只能为串中的字符，则有：
注意记录转移时的前驱与转移函数，根据前驱还原出方案即可。
总复杂度 (O(left(10|s|cdotsum |t_i|
ight)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) 的数字的个数。
(1le nle 10^{1201})，(1le mle 100)，(1le 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
", ACAM::DP());
return 0;
}
「NOI2011」阿狸的打字机
建议先阅读原题面后再阅读简述题面。
通过奇怪的方法给定 (n) 个字符串 (s_1sim s_n)，给定 (m) 次询问。
每次询问给定参数 (x)，(y)，求在字符串 (s_y) 中 (s_x) 的出现次数。
(1le 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| + mlog 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
", ans[i]);
return 0;
}
写在最后
参考资料：