前言
前置知识：
Trie的构建和简单应用KMP的思想
概念
构建
AC自动机实际上是在Trie中加入了fail指针的概念。
设\(S(i)\)表示节点\(i\)表示的字符串，\(\mathrm{Suf}(S)\)表示字符串\(S\)的所有后缀（除去自己）组成的集合，那么一个\(\mathrm{fail}\)指针代表的内容用形式化表示就是：
特别的，如果没有任何一个满足条件的没有任何一个节点所代表的字符串是\(S(j)\)的后缀，那么\(\mathrm{fail}(i)=\mathrm{ROOT}\)。
用人话来讲，就是从开头开始去掉尽可能少的字母，但是至少去除一个字母，使得所得到的新字符串依然在Trie中。
那么我们可以得到，从一个节点\(u\)开始，沿着\(\mathrm{fail}\)指针转跳，那么一定可以得到所有的，已经存入了Trie中的后缀。
那么显然可以得到下面的构造代码：
//ROOT = 0
queue<int> q;
void build_fail() {
for (int i = 0; i < 26; i++)
if (nd[0].ch[i]) q.push(nd[0].ch[i]), nd[nd[0].ch[i]].fail = 0;
else nd[0].ch[i] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i++) {
if (nd[u].ch[i])
q.push(nd[u].ch[i]),
nd[nd[u].ch[i]].fail = nd[nd[u].fail].ch[i];
else nd[u].ch[i] = nd[nd[u].fail].ch[i];
}
}
}
简单应用
单纯是AC自动机
[模板]AC自动机（加强版）
给定一个文本串和\(N\)个模式串，求出在文本串中出现最多的模式串集合以及最大的出现次数。
根据前面得到了理论，当我们从左往右扫描文本串的时候，如果当前位置对应的AC自动机节点为\(u\)，那么沿着\(\mathrm{fail}\)进行转跳，将沿途所有节点的计数变量cnt都加\(1\)。
代码：
#include <bits/stdc++.h>
using namespace std;
struct TreeNode { int fail, end_id, son[27]; } node[1000005];
struct Note {
int id, cnt;
friend bool operator < (Note a, Note b) {
return (a.cnt != b.cnt ? a.cnt > b.cnt : a.id < b.id);
}
} note[155];
int N, tot_node;
string T[155], S;
void insert(string& str, int ind) { ... }
void build_fail() { ... }
void AC_match() {
int l = S.length(), u = 0;
for (int i = 0; i < l; i++) {
u = node[u].son[S[i] - 'a'];
for (int j = u; j; j = node[j].fail)
note[node[j].end_id].cnt++;
}
}
int main() {
while (scanf("%d", &N), N) {
for (int i = 0; i <= tot_node; i++)
memset(node[i].son, 0, sizeof(node[i].son)), node[i].end_id = node[i].fail = 0;
tot_node = 0;
for (int i = 1; i <= N; i++)
cin >> T[i], insert(T[i], i), note[i].id = i, note[i].cnt = 0;
node[0].fail = 0;
cin >> S;
build_fail();
AC_match();
sort(note + 1, note + 1 + N);
cout << note[1].cnt << endl << T[note[1].id] << endl;
for (int i = 2; i <= N; i++)
if (note[i].cnt == note[i - 1].cnt) cout << T[note[i].id] << endl;
else break;
}
return 0;
}
[USACO15FEB]Censoring G
并不想概括题面，请大佬们自行点击链接查看。
可以发现题面中的一个很好的性质：给定的模式串不可能存在一个串是另一个的子串。
可以考虑用栈维护答案。同时记录扫描到文本串第\(i\)个位置时对应的AC自动机中的哪一个节点。
当我们从左往右扫文本串，到达位置\(p\)，当到达有某个节点\(u\)，如果\(S(u)\)是某一个模式串，那么我们可以将\(S(u)\)从栈中直接弹出（如果是手写栈的话可以直接s-=len[u]），接着将当前所在的节点设为当位置为\(p - len[u]\)对应的节点。
好了，问题来了，为什么我们不像先前那样将\(S(u)\)的所有存在与AC自动机中的后缀都看一遍,，看看是否在这些后缀中是否有模式串呢？
因为没有必要，首先节点\(u\)存在的充要条件就是以节点\(u\)为根的Trie子树中存在一个模式串，而很显然，这些模式串中任何一个，假设为\(S\),它的其中子串一定包含\(S(u)\)的所有后缀，假设\(S(u)\)所有存在于AC自动机中的后缀中有一个模式串\(T\)，那么\(T\)一定是\(S\)的子串，和题意矛盾，所以只需要看\(S(u)\)是不是模式串就好了。
代码(另一种码风)：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
queue<int> q;
struct ACm {
struct ACnode { int son[26], to[26], fail, end, len; } nd[maxn];
int nd_tot, rt;
ACm() { nd_tot = rt = 1; }
void insert(char* str) {
int len = strlen(str), u = rt;
for (int i = 0; i < len; i++) {
int ch = str[i] - 'a';
if (!nd[u].son[ch])
nd[u].son[ch] = ++nd_tot, nd[nd[u].son[ch]].len = nd[u].len + 1;
u = nd[u].son[ch];
}
nd[u].end = true;
}
void getfail() {
for (int i = 0; i < 26; i++)
if (nd[rt].son[i])
nd[nd[rt].to[i] = nd[rt].son[i]].fail = rt,
q.push(nd[rt].to[i]);
else nd[rt].to[i] = rt;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i++)
if (nd[u].son[i])
nd[nd[u].to[i] = nd[u].son[i]].fail = nd[nd[u].fail].to[i],
q.push(nd[u].to[i]);
else nd[u].to[i] = nd[nd[u].fail].to[i];
}
}
} A;
char S[maxn], T[maxn], ANS[maxn];
int pos[maxn], ans_len;
int main() {
int n, S_len;
scanf("%s\n%d", S+1, &n), S_len = strlen(S+1);
while (n--) scanf("%s", T), A.insert(T);
A.getfail(), pos[0] = A.rt;
for (int i = 1, u = A.rt; i <= S_len; i++) {
char ch = S[i] - 'a';
u = A.nd[u].to[ch], pos[++ans_len] = u, ANS[ans_len] = S[i];
if (A.nd[u].end)
ans_len -= A.nd[u].len, u = pos[ans_len];
}
for (int i = 1; i <= ans_len; i++) putchar(ANS[i]);
putchar('\n');
return 0;
}
AC自动机+DP
[USACO12JAN]Video Game G
设定字符集为\(\Sigma = \{\mathrm{'A','B','C'}\}\),给定\(N\)个模式串，可能会有重复，现在需要构建一个长度为\(k\)的文本串，使得这个文本串中模式串出现的次数尽可能多，输出最大的模式串出现次数。
首先构建一个AC自动机，其中每个节点额外记录下这个节点\(u\)代表的字符串中\(S(u)\)代表的模式串数量，加上\(\mathrm{Suf}(S(u))\)中所有的模式串个数，设为\(w(u)\)。
设\(f(i,j)\)表示已经构建出了长度为\(i\)的文本串，所在的节点为\(j\),那么可以使用填表法进行计算：
那么最终的答案为
[JSOI2007]文本生成器
给定一堆模式串，要求构建一个文本串，长度为\(m\)，满足该文本串中至少包含一个模式串，问构造方案数。
显然也是一个\(dp\)，有两种方法：
idea 1
设\(f(i,j,fl)\)表示已经构建出长度为\(i\)的字符串，所在节点为\(j\)，当前是否已经包含一个模式串，那么可以得到：
其中\(u.fl\)表示节点\(S(u)\)及其有后缀中是否包含至少一个模式串。
那么最终的答案为
idea 2
考虑更简单的容斥。
\(f(i,j)\)表示长度为\(i\),所在节点为\(j\)，文本串中不包含任何一个模式串的方案数，那么可以得到：
那么最终答案为：