AC自动机总结（个人笔记）
柒葉灬
2018-12-31 21:41:00
# AC自动机总结
--------
前置技能：$kmp$算法，$Tire$树。
AC自动机和$Tire$树一样，不做重复的运算，所以也有一个$nxt$数组，即在匹配失败的时候快速跳到**最长后缀**位置。
模板：
```cpp
void insert(char *str){
int x=0,len=strlen(str);
for(int i=0;i<len;i++){
int &pos=son[x][str[i]-'a'];
if(!pos)pos=++tot;
x=pos;
}
}
void Getnxt(){
queue<int>q;
for(int i=0;i<26;i++)
if(son[0][i])q.push(son[0][i]);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<26;i++)
if(son[x][i]){
nxt[son[x][i]]=son[nxt[x]][i];//A
q.push(son[x][i]);
}else son[x][i]=son[nxt[x]][i];//B
}
}
```
为什么A的位置不需要一直跳了呢？，因为如果$nxt[x]$已经是前面的最佳匹配，
此时若$nxt[x]$有$i$，则最佳后缀肯定指向$son[nxt[x]][i]$，
否则需要向上跳，而B的位置已经处理出来了，所以仍然是$son[nxt[x]][i]$
-------
入门题目：[专题A](https://cn.vjudge.net/contest/277428#problem/A)
-------
初学题目：[专题B](https://cn.vjudge.net/contest/277428#problem/B)
注意AC自动机是以询问的串建的，不是以目标串建的。
写了这道题目就很清楚了
----------
[专题D](https://cn.vjudge.net/contest/277428#problem/D)
由于要判断是否重叠，所以需要记录出现的位置，用vector存就行了，防止一样的串一直询问，所以dp一下就行了。
----------
[专题F](https://cn.vjudge.net/contest/277428#problem/F)
AC自动机+DP
一道很好的题目，注意用AC自动机匹配一定不能 **先出不合法 后去除**，这样子会错。
----------
[专题G](https://cn.vjudge.net/contest/277428#problem/G)
AC自动机+状压DP
-----------
[专题J](https://cn.vjudge.net/contest/277428#problem/J)
AC自动机+矩阵乘法（矩阵快速幂）
技巧：**看到状态转移类型，切转移次数有$10^9$这么大肯定是矩阵快速幂**
---------
[专题N](https://cn.vjudge.net/contest/277428#problem/N)
这题需要把**fail树**拉出来了，这里写的是**可持久化线段树**，在线，（听说还有离线的线段树合并）。
因为需要找最长前缀后缀，所以要从前面一个字符串的位置一直跳nxt数组，
直到跳到了有被后面一个字符串覆盖的节点，则那个节点的深度就是答案，
用可持久化线段树动态开点插入就行了。
代码：
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+5;
bool cur1;
int n,m,a,b;
int tot,to[maxn],dep[maxn],nxt[maxn],son[maxn][4];
char str[maxn];
vector<int>T[maxn];
struct SegTree{
static const int maxm=maxn*22;
int tot,rt[maxn],lson[maxm],rson[maxm],val[maxm];
void clear(){
tot=0;
memset(rt,0,sizeof(rt));
memset(lson,0,sizeof(lson));
memset(rson,0,sizeof(rson));
}
void insert(int &rt,int od,int l,int r,int x,int pos){
rt=++tot;
if(l==r){
val[rt]=pos;
return;
}
lson[rt]=lson[od];
rson[rt]=rson[od];
int mid=l+r>>1;
if(x<=mid)insert(lson[rt],lson[od],l,mid,x,pos);
else insert(rson[rt],rson[od],mid+1,r,x,pos);
}
int Query(int rt,int l,int r,int x){
if(!rt)return -1;
if(l==r)return val[rt];
int mid=l+r>>1;
if(x<=mid)return Query(lson[rt],l,mid,x);
else return Query(rson[rt],mid+1,r,x);
}
int solve(int a,int b){
return Query(rt[to[a]],1,n,b)+1;
}
void add(int a,int x,int pos){
insert(rt[a],rt[a],1,n,x,pos);
}
void Give(int a,int b){
rt[a]=rt[b];
}
}S;
void insert(char *str,int p){
int x=0;
int len=strlen(str);
for(int i=0;i<len;i++){
if(str[i]=='T')str[i]='B';
else if(str[i]=='G')str[i]='D';
int &pos=son[x][str[i]-'A'];
if(!pos){
pos=++tot;
dep[pos]=i;
}
x=pos;
T[x].push_back(p);
}
to[p]=x;
}
void update(int y){
for(int j=0;j<T[y].size();j++){
S.add(y,T[y][j],dep[y]);
}
}
void Getnxt(){
queue<int>q;
for(int i=0;i<4;i++)
if(son[0][i]){
update(son[0][i]);
q.push(son[0][i]);
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<4;i++)
if(son[x][i]){
int y=son[x][i];
nxt[y]=son[nxt[x]][i];
S.Give(y,nxt[y]);
update(y);
q.push(y);
}else son[x][i]=son[nxt[x]][i];
}
}
void clear(){
for(int i=0;i<=tot;i++)
T[i].clear();
memset(nxt,0,sizeof(nxt));
memset(son,0,sizeof(son));
tot=0;
S.clear();
}
bool cur2;
int main(){
// double sz=&cur2-&cur1;
// cout<<sz/1024<<endl;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++){
scanf("%s",str);
insert(str,i);
}
dep[0]=-1;
Getnxt();
while(m--){
scanf("%d%d",&a,&b);
printf("%d\n",S.solve(a,b));
}
clear();
}
return 0.0;
}
```
--------
[专题O](https://cn.vjudge.net/contest/277428#problem/O)
进阶题目：把fail树拉出来重新建一颗树。
设第x个单词为最后的最大贡献为$f(x)$ 则答案肯定是$f(x)=A[x]+max(f(i))$。
所以只要得到$max(f(i))$就行了
>所取的$f(i)$中，i是x的子串
我们知道，若第$i$个单词是第$x$个单词的子串，则$x$字符串中必定有一个位置通过nxt可以跳到$i$单词的末尾。
我们只要维护这个就行了。
我们把fail树拉出来，每次把答案加到末尾节点，变成了修改子树最大值问题了。
代码：
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=2e4+5,maxm=3e5+5;
bool cur1;
int n,A[maxn],to[maxn];
int tot;
int fa[maxm];
int nxt[maxm];
int son[maxm][26];
char str[maxm];
struct Graph{
int id,to[maxm],nxt[maxm],head[maxm];
void add_edge(int u,int v){
to[++id]=v;
nxt[id]=head[u];
head[u]=id;
}
}G;
struct SegTree{
struct node{
int l,r,mx,lazy;
void tomax(int x){
mx=max(mx,x);
lazy=max(lazy,x);
}
}tree[maxm<<2];
void up(int p){
tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx);
}
void down(int p){
int &pos=tree[p].lazy;
if(pos){
tree[p<<1].tomax(pos);
tree[p<<1|1].tomax(pos);
pos=0;
}
}
int id,L[maxm],R[maxm];
void dfs(int x){
L[x]=++id;
for(int i=G.head[x];i;i=G.nxt[i])
dfs(G.to[i]);
R[x]=id;
}
void build(int l,int r,int p){
tree[p]=(node){l,r,0,0};
if(l==r)return;
int mid=l+r>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
}
void update(int l,int r,int pos,int p){
if(tree[p].l==l&&tree[p].r==r)
return tree[p].tomax(pos);
down(p);
int mid=tree[p].l+tree[p].r>>1;
if(r<=mid)update(l,r,pos,p<<1);
else if(l>mid)update(l,r,pos,p<<1|1);
else {
update(l,mid,pos,p<<1);
update(mid+1,r,pos,p<<1|1);
}
up(p);
}
int Query(int x,int p){
if(tree[p].l==tree[p].r)
return tree[p].mx;
down(p);
int mid=tree[p].l+tree[p].r>>1;
if(x<=mid)return Query(x,p<<1);
else return Query(x,p<<1|1);
}
void Build(){
id=0;
dfs(0);
build(1,id,1);
}
void add(int a){
update(L[to[a]],R[to[a]],A[a],1);
}
int solve(int a){
int mx=0,x=to[a];
while(x){
mx=max(mx,Query(L[x],1));
x=fa[x];
}
return mx+A[a];
}
}S;
void insert(char *str,int p){
int x=0;
int len=strlen(str);
for(int i=0;i<len;i++){
int &pos=son[x][str[i]-'a'];
if(!pos)pos=++tot;
x=pos;
}
to[p]=x;
}
void Getnxt(){
queue<int>q;
for(int i=0;i<26;i++)
if(son[0][i]){
q.push(son[0][i]);
fa[son[0][i]]=0;
G.add_edge(0,son[0][i]);
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<26;i++)
if(son[x][i]){
nxt[son[x][i]]=son[nxt[x]][i];
fa[son[x][i]]=x;
G.add_edge(nxt[son[x][i]],son[x][i]);
q.push(son[x][i]);
}else son[x][i]=son[nxt[x]][i];
}
}
void clear(){
for(int i=0;i<=tot;i++){
nxt[i]=0;
memset(son[i],0,sizeof(son[i]));
G.head[i]=0;
}
G.id=tot=0;
}
bool cur2;
int main(){
// double sz=&cur2-&cur1;
// cout<<sz/1024<<endl;
for(int _,cas=(cin>>_,1);cas<=_;cas++){
clear();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s%d",str,&A[i]);
insert(str,i);
}
Getnxt();
S.Build();
int ans=0;
for(int i=1;i<=n;i++){
A[i]=S.solve(i);
ans=max(ans,A[i]);
S.add(i);
}
printf("Case #%d: %d\n",cas,ans);
}
return 0.0;
}
```
------------
[专题P](https://cn.vjudge.net/contest/277428#problem/P)
题解写在203上。