这是一个解决多模式串的算法
不是accept自动机
问题
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
模式串总长<=,文本串总长<=
对于字符串匹配，我们一定能想到kmp算法
而它的复杂度为O(s1+s2)，其中s1为模式串长度，s2为文本串长度
如果让它做n次匹配
复杂度为O(n*(s1+s2))
我们姑且当作O(n*s2)来算，只要n达到100，运算数量就会达到一亿
这是我们无法承受的复杂度
但AC自动机能帮我们解决，并有一个优秀的复杂度
算法
主要用字典树Trie来实现
AC自动机考虑将所有模式串放入Trie中
与普通Trie不同的是
会加进fail[x]这个数组
它的作用在于
当一个节点失配时能直接跳到失配前的后缀节点上
当一个模式串被匹配成功时，把所有此串的后缀串都试一下是否成功
什么意思？
我们可以看看下图
蓝边代表fail边
当AKIOI这个单词匹配成功后，我们会通过fail边将IOI,OI这两个单词也拿下
而如何得到fail数组呢
这是AC自动机的重中之重
我们考虑到fail[x]的定义
指向从root到x这条路径上组成的单词的一个字典树中有的后缀
考虑
fail[x]=trie[fail[k]][i]
k为x的父亲节点
i为k-x这条边所代表的字母
那么这一句话就是说
x的fail就是k的fail的i儿子
但这一句话可能指空，就是说本来能指向一个节点但没指到
for(int i=0;i<26;i++){
int tmp=trie[k][i];
if(tmp)
fail[tmp]=trie[fail[k]][i];
else
trie[k][i]=trie[fail[k]][i];
}
看到上面的代码
为何要改变原有Trie树结构呢
我们要保证fail能指向最优秀的地方
那遍历顺序呢，我们能看到我们的fail是依托父亲节点得到的
而改变Trie树结构，应使深度浅的先改好(fail指向的一定比当前节点深度小)
故bfs能帮我们解决问题
可以参考这份代码
void pre(){
for(int i=0;i<26;i++)
if(trie[root][i])
q.push(trie[root][i]);
while(!q.empty()){
int k=q.front();
q.pop();
for(int i=0;i<26;i++){
int tmp=trie[k][i];
if(tmp){
fail[tmp]=trie[fail[k]][i];
q.push(tmp);
}
else
trie[k][i]=trie[fail[k]][i];
}
}
return ;
}
那把fail构建好了
怎么查呢
与字典树的查类似
直接往下走即可
走一个点就疯跳fail边
注意tot[j]=-1这里
代表我们每个节点最多搜一次
复杂度O(s1总)，s1为模式串长度
int query(string s){
int ans=0;
int x=root;
for(int i=0;i<s.size();i++){
x=trie[x][s[i]-'a'];
for(int j=x;tot[j]!=-1;j=fail[j]){
ans+=tot[j];
tot[j]=-1;
}
}
return ans;
}
模板完整代码
#include<bits/stdc++.h>
using namespace std;
int root,cnt;
int fail[1000005];
int trie[1000005][26];
int tot[1000005];
queue<int>q;
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
void ins(string s){
int x=root;
for(int i=0;i<s.size();i++){
if(!trie[x][s[i]-'a'])
trie[x][s[i]-'a']=++cnt;
x=trie[x][s[i]-'a'];
}
tot[x]++;
return ;
}
void pre(){
for(int i=0;i<26;i++)
if(trie[root][i])
q.push(trie[root][i]);
while(!q.empty()){
int k=q.front();
q.pop();
for(int i=0;i<26;i++){
int tmp=trie[k][i];
if(tmp){
fail[tmp]=trie[fail[k]][i];
q.push(tmp);
}
else
trie[k][i]=trie[fail[k]][i];
}
}
return ;
}
int query(string s){
int ans=0;
int x=root;
for(int i=0;i<s.size();i++){
x=trie[x][s[i]-'a'];
for(int j=x;tot[j]!=-1;j=fail[j]){
ans+=tot[j];
tot[j]=-1;
}
}
return ans;
}
int main(){
int n;
string st;
n=read();
for(int i=1;i<=n;i++){
string s;
cin>>s;
ins(s);
}
pre();
cin>>st;
printf("%d",query(st));
return 0;
}
【模板】AC自动机（加强版）
对于加强版
数据范围很小
模式串总长不超过10500
就直接把tot[j]=-1的剪枝去掉
然后直接暴力跑
#include<bits/stdc++.h>
using namespace std;
int root,cnt;
string p[155];
int s1[150*70+5];
int fail[150*70+5];
int trie[150*70+5][26];
int tot[150*70+5],sum[150*70+5];
int len=0;
int a[155];
queue<int>q;
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
bool cmp(int i,int j){
return s1[i]<s1[j];
}
void ins(string s,int id){
int x=root;
for(int i=0;i<s.size();i++){
if(!trie[x][s[i]-'a'])
trie[x][s[i]-'a']=++cnt;
x=trie[x][s[i]-'a'];
}
tot[x]++;
s1[x]=id;
return ;
}
void pre(){
for(int i=0;i<26;i++)
if(trie[root][i])
q.push(trie[root][i]);
while(!q.empty()){
int k=q.front();
q.pop();
for(int i=0;i<26;i++){
int tmp=trie[k][i];
if(tmp){
fail[tmp]=trie[fail[k]][i];
q.push(tmp);
}
else
trie[k][i]=trie[fail[k]][i];
}
}
return ;
}
int query(string s){
int ans=0;
int x=root;
for(int i=0;i<s.size();i++){
x=trie[x][s[i]-'a'];
for(int j=x;j;j=fail[j]){
if(tot[j]){
sum[j]++;
if(sum[j]>ans){
ans=sum[j];
len=1;a[len]=j;
}
else if(sum[j]==ans)
a[++len]=j;
}
}
}
return ans;
}
int main(){
while(1){
int n;
string st;
n=read();
if(!n)return 0;
len=0;
cnt=0;
memset(s1,0,sizeof(s1));
memset(trie,0,sizeof(trie));
memset(fail,0,sizeof(fail));
memset(tot,0,sizeof(tot));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
string s;
cin>>s;
p[i]=s;
ins(s,i);
}
pre();
cin>>st;
int ans=query(st);
printf("%d\n",ans);
sort(a+1,a+len+1,cmp);
for(int i=1;i<=len;i++)
cout<<p[s1[a[i]]]<<endl;
}
return 0;
}
【模板】AC自动机（二次加强版）
对于二次加强版
前面O(s2*s1)这样级别的复杂度过不去了
我们要把它优化回去
考虑根据fail边可以建出一个DAG
而我们暴力计算次数时都是沿fail边跳
显然设sum[x]表示x这个节点被计算的次数
若fail[x]指向v节点的话
sum[v]里应包含所有的sum[u]
那就直接拓扑排序
然后累加sum即可
放上query和topo代码
void query(string s){
int x=root;
for(int i=0;i<s.size();i++){
x=trie[x][s[i]-'a'];
sum[x]++;
}
return ;
}
void topo(){
while(!q.empty())q.pop();
for(int i=1;i<=cnt;i++)
if(!rd[i])
q.push(i);
while(!q.empty()){
int k=q.front();
q.pop();
if(!fail[k])continue;
sum[fail[k]]+=sum[k];
rd[fail[k]]--;
if(!rd[fail[k]])
q.push(fail[k]);
}
return ;
}
二进制分组AC自动机
由于AC自动机是一个离线算法
当我们需要在线加入单词
强制在线查询时
我们可以考虑二进制分组AC自动机
就是说，每一个字典里的单词
进来时考虑先单独自己成一个AC自动机
然后看有没有AC自动机里的单词数量和该AC自动机单词数量相同
有的话就重构合并(就是把这两个AC自动机的单词一个个重新插到新的AC自动机里)
我们考虑复杂度
我们最多有类似这样的自动机
1，2，4，8，16...,2^k
上面的数代表自动机内单词数量
那么1+2+4+...+2^k=n
也就是2^(k+1)-1=n
则有log个自动机
然后对于每一个单词，因为k为log级别
最多重构k(log)次
考虑查询
我们每次在这log个自动机里分别跑一边查询
综上，我们相当于复杂度多带一个log
非常nice
AC自动机上的dp与fail树的应用
字符串上的匹配问题可以用AC自动机解决
方案，计数等问题可以用dp解决
通常定义表示字符串第位，状态为AC自动机上的点的答案
树指AC自动机节点的指针所构成的树形结构
由于这是一棵树，dfs序，树剖，等与树有关的知识点都可以套在树上
最经典的是多次询问串在中的出现次数
相当于找树上属于的节点的到根的路径上有多少个的末尾节点
