AC自动机基础
简介
AC自动机(Aho-Corasick automaton), 也可以叫ACAM。
是一种复杂度线性的字符串算法，适用于字符串匹配及相关问题
算法思路
总的来说就是将kmp的next数组的思想运用到Trie树上
但是与next数组不同的是：
-
名字不同，ACAM里的叫做fail -
fail指针指向的是trie树上当前字符串的出现过的最长后缀代表的节点,
形式化的：
对于节点u，令Trie树上根到u的路径代表的字符串为 (S_{1...u})
那么 (fail_u ightarrow v) 满足 (S_{1...v}) 为 (S_{1...u}) 的最长后缀
因为是最长的后缀，所以fail指针的指向是唯一的(很重要哦)
算法流程
- 将模式串(小串)全部插入Trie树
- 计算fail数组并完成Trie图
- 将文本串(匹配的大串)放入Trie图进行匹配
怎么利用fail指针进行多串同时匹配?
当一个结点 (u) 的某个儿子指针(k)为空,其代表了(S_{1...u})这个字符串接下来不会出现k所代表的字符,也就是失配了.
但是!!! 可能存在另一个字符串还能接着匹配,那么这个字符串必定是(S_{1...u})的一个后缀(空串也算后缀嘛)
所以失配后跳转到节点(fail_u)继续进行匹配即可,而当前串的后缀的后缀一定也是当前串的后缀,(fail_u)指向的是最长的后缀,因此可以遍历到所有后缀
什么是Trie图
Trie图是一种路径压缩的形式
为了避免匹配时重复跳转fail而降低复杂度,直接将每个节点的空的儿子指针指向它的后缀串里有该儿子的位置也就是 (t[u].ch[i]=t[fail[u]].ch[i]), 当然(fail_u)也有可能不存在这个儿子,那么接着跳fail即可
剩下的具体细节都会在代码里注释
代码
struct Trie{
int ch[28], tg;
// tg是每个节点有多少个模式串以此结尾
}t[_<<5];
char T[_], s[_];
#define son(u) t[u].ch[s[i]-'a']// 代码消失术
void insert() //当前插入的串是S
{
int u=1, len=strlen(s+1);
for(re int i=1;i<=len;++i)
{
if(!son(u)) son(u)=++tot;
u=son(u);
}
t[u].tg++;
}
void build()
{
queue<int >q; q.push(1); //bfs遍历Trie树
for(re int i=0;i<26;++i) t[0].ch[i]=1;
while(!q.empty())
{
int u=q.front(); q.pop();
for(re int i=0;i<26;++i) //枚举儿子
{
if(!t[u].ch[i]) t[u].ch[i]=t[fail[u]].ch[i]; //没有该儿子
else
{
q.push(t[u].ch[i]);
int v=fail[u];
while(v && !t[v].ch[i]) v=fail[v]; //跳过该儿子为空的后缀
fail[t[u].ch[i]]=t[v].ch[i]; //计算儿子节点的fail
}
}
}
}
AC自动机进阶
fail树
要是想知道每个模式串在文本串中出现的次数,该怎么办呢?
显然可以把匹配路径上的每个节点的fail(和fail的fail...等等)全都遍历一遍
但这样统计答案显然不优
仔细想想,不难发现实际上在不断跳fail计算贡献的时候很多的路径是重复的
如何避免计算重复路径?
因为每个节点的fail是唯一的,并且fail指针一定会指向深度比自己更浅的点
因此所有的fail指针构成了一颗外向树!!!
而一个点的结尾标记,会对所有它到根的路径上的点都产生贡献!
因此,我们将fail指针反向后可以建出一颗树
直接对树进行各种操作(树链剖分)可以大幅降低模式串之间的相互贡献
DP
这实际上就是个套路啦
一般是记 f[i][u] 表示文本串匹配到了i位,匹配到了trie树上的u号点的答案
转移时,枚举i, u, k
计算 (f[i-1][u]) 对于(f[i] [t[u].ch[k]])的贡献即可