AC自动机学习笔记
AC自动机学习笔记
用途
一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。
思想
要搞懂AC自动机,先得有模式树(Trie树)Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步:构造一棵Trie树,构造失败指针和模式匹配过程。
与KMP类似,AC自动机对于普通暴力的优化方式即是在与当前模式串失配后,找到其他模式串中与字符串公共前后缀最长的一个模式串,并且继续进行匹配。
譬如对于模式串①“ABCDG”,②”BCDE”,与文本串”ABCDE”,在与模式串①匹配到S[5]=“E”时,发生了失配,快速找到另一个模式串的前缀与匹配前(未匹配S[5]时)的后缀最长的一个模式串,也就是②(”BCD”),然后继续匹配。
复杂度 O(\sum n+m)
注:公共前后缀指串 s1 与串 s2,存在i_{s1},j_{s2}使s1的prefix(i_{s1})=subfix(j_{s2})
注:prefix(i) 指s[1….i],subfix(i) 指 s[i….n]
注:rt 指 Trie 树的根节点,s[1….i] 指由字符 s[1],s[2],….s[i] 所构成的长度为i的字符串
构建
首先将所有模式串插入 Trie树 中。
其次构造 Fail 数组。
Fail 数组含义
Fail[x] 表示 与字符串 s[rt….x] (从 Trie 的根到节点 x 所组成的字符串)所具有最长公共前后缀的字符串是 字符串 s[rt….Fail[x]]。类似于KMP算法中的 next 数组
Fail数组构造方法
通常使用BFS的方式构造,这样可以保证我们构造Fail[x]的顺序是由其在 Trie 树中深度从小到大的。(逐层扩展)
Fail[x]默认为空,指向 rt
① 将 rt 的所有儿子加入队列
② 寻找一个对于节点 x , 由 儿子 y , 不妨假设节点 x 所映射的字符为 ‘a’,节点 y 所映射的字符为 ‘b’
如果在 Trie 树中,Fail[x]节点的儿子中存在与 y 相应的字符(在这里也就是’b’),
那么 Fail[y] 便指向 Fail[x] 的这个儿子。
否则令 x= Fail[x],重复②操作。
其中关于“最长”的证明是显然的。
void Fail_Build(){
std::queue<int> q;
q.push(rt);//rt=0
memset(fail,0,sizeof(fail));
while(!q.empty()){
int now=q.front();q.pop();
for(int i=0;i<26;++i){
if(trie[now][i]){
int k=now;
while(k!=rt){
k=fail[k];
if(trie[k][i]){
fail[trie[now][i]]=trie[k][i];
break;
}
}
q.push(trie[now][i]);
}
}
}
}
匹配
对于匹配,类似于 Tire树 查找的过程,我们不断在 Trie 树上爬,对于未匹配的过程,我们从当前所处的节点 x 跳转到 Fail[x] 处,继续匹配。而如果当前节点 x 被打上了 Trie 树的 end 标记 (当前所处字符是某个匹配串的结尾),那么就说明文本串完整地匹配了这个匹配串。
inline int Find(char *s,int len){
int now=rt,ans=0;
for(int i=1;i<=len;++i){
while(now&&!tire[now][s[i]-'a'])
now=fail[x];
now=trie[now][s[i]-'a'];
int k=now;
while(k!=rt){
if(end[k])
ans++;// match sucessfully.
k=fail[k];
}
}
return ans;
}
优化与扩展
Trie 图
我们发现,在构造 Fail 数组时,我们不断向前回溯直到找到所对应的 Fail 指针,该策略效率偏低。考虑使用Trie 图优化。Trie 图实际上是指在所有模式串全部插入 Trie 树后,Tire 树的形态已经固定后,对于节点 x ,如果不存在 Trie[x][y],那么就令Trie[x][y]=Trie[Fail[x]][y]。对于构造 Fail 数组时 这是一个递归的过程,可能需要模拟便于理解为什么不破坏其仍为“最长”的性质。对于匹配时,每次可以直接将节点跳转到Trie[x][S[i]-‘a’]。
构造:
for(int i=0;i<26;++i){
if(trie[x][i]){
fail[trie[x][i]]=trie[fail[x]][i];
q.push(trie[x][i]);
}
else
trie[x][i]=trie[fail[x]][i];
}
匹配:
void find(string s){
int len=s.length();
int k=rt;
for(int i=0;i<len;++i){
k=trie[k][s[i]-'a'];
int t=k;
while(t){
ans++;
}
}
}
完整代码:
// Luogu P3796
#include<bits/stdc++.h>
using std::string;
using std::map;
map<int,string> mp;
const int N = 1e5;
int n;
char s[N];
int trie[N][26];
int fail[N],end[N],rt,tot;
int tag[N];
void insert(string s){
int len=s.length();
int now=rt;
for(int i=0;i<len;++i){
if(!trie[now][s[i]-'a'])
trie[now][s[i]-'a']=++tot;
now=trie[now][s[i]-'a'];
}
end[tot]++;
mp[tot]=s;
}
void build(){
std::queue<int> q;
for(int i=0;i<26;++i){
if(trie[rt][i])
q.push(trie[rt][i]);
}
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<26;++i){
if(trie[x][i]){
fail[trie[x][i]]=trie[fail[x]][i];
q.push(trie[x][i]);
}
else
trie[x][i]=trie[fail[x]][i];
}
}
}
void find(string s){
int len=s.length();
int k=rt;
for(int i=0;i<len;++i){
k=trie[k][s[i]-'a'];
int t=k;
while(t){
tag[t]+=end[t];
t=fail[t];
}
}
}
int main(){
while(scanf("%d",&n)&&n){
memset(trie,0,sizeof(trie));
memset(fail,0,sizeof(fail));
memset(tag,0,sizeof(tag));
memset(end,0,sizeof(end));
rt=tot=0;
for(int i=1;i<=n;++i){
string s;
std::cin>>s;
insert(s);
}
build();
string s;
std::cin>>s;
find(s);
int wh=0;
for(int i=1;i<=tot;++i)
if(tag[i]>tag[wh]) wh=i;
std::cout<<tag[wh]<<std::endl;
for(int i=1;i<=tot;++i){
if(tag[i]==tag[wh]){
std::cout<<mp[i]<<std::endl;
}
}
//std::cout<<tag[wh]<<std::endl<<mp[wh]<<std::endl;
}
return 0;
}
Fail 树
我们将每个节点 x 与其指向的 Fail 数组的点 Fail[x] 连边(Fail[x] 为父亲)
add(Fail[x],x)
则会发现所构造出的图是树形态的,我们称为 Fail 树
①它的每个点都是一个字符串的前缀,而且每个字符串的每个前缀在这棵树上都对应着一个点。
②每个点的父节点的字符串都是这个点字符串的后缀,并且树上没有更长的它的后缀。
也就是说,所有以字符串S[1…i]的为结尾的字符串都在 i 的子树内。
本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。
本文永久链接: http://www.mayflyyh.com/archives/500
一条评论
%%%