自动机
AC 自动机以 Trie 为骨架、结合 KMP 的失配指针思想处理多模式串匹配，用 BFS 构造 fail 指针并把 Trie 改造为字典图，使每次转移 O(1)。后缀数组把所有后缀按字典序排序，配合 height 数组解决本质不同子串数、最长重复子串等问题。后缀自动机是接受一个串全部后缀的最小自动机，状态对应 endpos 集合相同的子串、规模线性，借助 parent 树与 len 处理子串计数、两串最长公共子串。广义后缀自动机把它推广到一组字符串上。
参考资料
AC 自动机
AC 自动机（Aho–Corasick Automaton）以 Trie 为骨架，结合 KMP 的失配指针思想，用于多模式串匹配。
建立过程分两步：将所有模式串插入 Trie；再用 BFS 对每个结点构造 fail 指针，使其指向该结点对应字符串的最长后缀状态。构建完成后同时将 Trie 改造为字典图——若字符 的子结点不存在，则令其指向 fail 结点的 子结点，保证每次转移 。查询时在字典图上逐字符转移，沿 fail 链累加匹配计数。设模式串总长为 ，文本串长为 ，字符集大小为 ，构建复杂度为 ，查询复杂度为 （连字典图后）。
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
int son[N][26],fail[N],cnt[N];
int tot=0;
void insert(string s)
{
int u=0;
for(auto c:s)
{
int x=c-'a';
if(!son[u][x])son[u][x]=++tot;
u=son[u][x];
}
cnt[u]++;
}
void build()
{
queue<int> q;
for(int i=0;i<26;i++)if(son[0][i])q.push(son[0][i]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(son[u][i])
{
fail[son[u][i]]=son[fail[u]][i];
q.push(son[u][i]);
}
else
{
son[u][i]=son[fail[u]][i];
}
}
}
}
int query(string s)
{
int u=0,res=0;
for(auto c:s)
{
u=son[u][c-'a'];
for(int j=u;j&&cnt[j]!=-1;j=fail[j])
{
res+=cnt[j];
cnt[j]=-1;
}
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
insert(s);
}
build();
string t;
cin>>t;
cout<<query(t)<<'\n';
return 0;
}
后缀数组简介
后缀数组（Suffix Array，SA）把字符串的所有后缀按字典序排序， 为排名第 的后缀起点， 为其逆。常用倍增法 构建，也有 SA-IS 等 做法。
配合 height 数组（排名相邻两后缀的最长公共前缀），后缀数组能解决本质不同子串数、可重叠/不可重叠最长重复子串等一类子串问题。
后缀自动机
后缀自动机（Suffix Automaton，SAM）是能接受一个字符串所有后缀的最小确定有限自动机。它的每个状态对应一组 （结束位置集合）相同的子串，状态数与转移数都是 ，可在线 构建。
借助 树（按 的包含关系）与各状态的 ，SAM 能高效解决本质不同子串计数、子串出现次数、两串最长公共子串等问题。
广义后缀自动机
广义后缀自动机 是后缀自动机在多个字符串上的推广，能接受一组字符串的所有后缀。把所有串建成一棵 Trie 后在其上构建，或逐串插入时在已有转移处特判，即得一个大小为 的自动机，可统计多串的本质不同子串等。