前言
本来时今年寒假学的，当时回家比较早没学完也没学明白，打模拟赛却多次用到，所以重学一下。
原理与定义
即 字典树（trie 树）加 \(fail\) 指针，\(fail\) 指针等同于 kmp 的 \(next\) 数组，匹配前缀的最长后缀，\(fail\) 指针单独拎出来构成一颗失配树（fail 树）。
插入同 trie 树，全部插完后建 fail 树，对于 \(y=son(x,i),z=fail(x)\)，若存在 \(son(z,i)\) 则 \(fail(y)=son(z,i)\)，否则另 \(son(x,i)=son(z,i)\) 来扩展 tire 树。（\(son(p,c)\) 指节点 \(p\) 边权为 \(c\) 的子节点）。
发现扩展后 trie 树不是树了反而存在环，由此直接跑 AC 自动机上的 trie 树是可以找到环的，部分题利用了这个性质。
P3808 AC 自动机（简单版）
由于每个串不能被重复统计，所以查询时暴力跳 \(fail\) 并标记，若被标记过停止即可，这样 AC 自动机上每个点最多被跳一次，复杂度是正确的。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int tot,n;
struct aa {int son[26],sum,fail;}trie[N];
void insert(string s)
{
int p=0,len=s.size();
for(int i=0,c;i<len;i++)
{
c=s[i]-'a';
if(!trie[p].son[c]) trie[p].son[c]=++tot;
p=trie[p].son[c];
}
trie[p].sum++;
}
void build()
{
queue<int>q;
for(int i=0;i<26;i++) if(trie[0].son[i])
q.push(trie[0].son[i]);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0,y,z;i<26;i++)
{
y=trie[x].son[i],z=trie[x].fail;
if(!y) {trie[x].son[i]=trie[z].son[i]; continue;}
trie[y].fail=trie[z].son[i];
q.push(y);
}
}
}
int ask(string s)
{
int p=0,ans=0,len=s.size();
for(int i=0,c,k;i<len;i++)
{
c=s[i]-'a';
for(int j=trie[p].son[c];j&&trie[j].sum!=-1;j=trie[j].fail)
ans+=trie[j].sum,trie[j].sum=-1;
p=trie[p].son[c];
}
return ans;
}
signed main()
{
read(n);
string s;
for(int i=1;i<=n;i++)
{
cin>>s;
insert(s);
}
build();
cin>>s;
write(ask(s));
}
拓扑优化
若查询出现次数，那么每个点都可以被重复统计，这样再暴力跳 \(fail\) 复杂度就假了，发现对于一个点被统计到，那么 fail 树上他到根节点这一条链都要被统计一遍，由此可以最后在 fail 树上拓扑优化，这样匹配的时候只每个节点只跳他自己的 fail 即可。
P3796 AC 自动机（简单版 II）
这个可以暴力跳 \(fail\) 水过去。
P5357 【模板】AC 自动机&P3966 [TJOI2013] 单词
做法上述。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e6+10,M=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,tot,deg[M],cnt[M],to[M];
char s[M],t[N];
struct aa {int son[26],fail,ans,id;}trie[M];
void insert(char s[],int id)
{
int p=0,len=strlen(s);
for(int i=0,c;i<len;i++)
{
c=s[i]-'a';
if(!trie[p].son[c]) trie[p].son[c]=++tot;
p=trie[p].son[c];
}
trie[p].id=trie[p].id?trie[p].id:id;
to[id]=trie[p].id;
}
void build()
{
queue<int>q;
for(int i=0;i<26;i++) if(trie[0].son[i])
q.push(trie[0].son[i]);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0,y,z;i<26;i++)
{
y=trie[x].son[i],z=trie[x].fail;
if(!y) {trie[x].son[i]=trie[z].son[i]; continue;}
trie[y].fail=trie[z].son[i];
deg[trie[y].fail]++;
q.push(y);
}
}
}
void ask(char s[])
{
int p=0,len=strlen(s);
for(int i=0;i<len;i++)
{
p=trie[p].son[s[i]-'a'];
trie[p].ans++;
}
}
void topo()
{
queue<int>q;
for(int i=0;i<=tot;i++) if(deg[i]==0) q.push(i);
while(!q.empty())
{
int x=q.front(); q.pop();
if(trie[x].id) cnt[trie[x].id]=trie[x].ans;
int y=trie[x].fail;
deg[y]--,trie[y].ans+=trie[x].ans;
if(deg[y]==0) q.push(y);
}
}
signed main()
{
read(n);
for(int i=1;i<=n;i++) scanf("%s",s),insert(s,i);
build(),scanf("%s",t),ask(t),topo();
for(int i=1;i<=n;i++) write(cnt[to[i]]),puts("");
}
可持久化字符串
某次模拟赛的，链接挂上面了。
匹配最长前缀
P5231 [JSOI2012] 玄武密码
模式串都扔到 AC 自动机里，单后匹配一遍母串处理处每个节点是否能能匹配母串节点，最后再把模式串扔进去跑一遍就行了。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e7+10,M=1e5+10,L=110;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tot;
char s[M][L],t[N];
struct aa {int son[4],fail; bool vis;}trie[N];
int val(char x) {return x=='E'?0:(x=='S'?1:(x=='W'?2:3));}
void insert(char s[])
{
int p=0,len=strlen(s);
for(int i=0,c;i<len;i++)
{
c=val(s[i]);
if(!trie[p].son[c]) trie[p].son[c]=++tot;
p=trie[p].son[c];
}
}
void build()
{
queue<int>q;
for(int i=0;i<4;i++) if(trie[0].son[i])
q.push(trie[0].son[i]);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0,y,z;i<4;i++)
{
y=trie[x].son[i],z=trie[x].fail;
if(!y) {trie[x].son[i]=trie[z].son[i]; continue;}
trie[y].fail=trie[z].son[i],q.push(y);
}
}
}
void ask()
{
for(int i=0,p=0,c,j;i<n;i++)
{
p=j=trie[p].son[val(t[i])];
while(j&&!trie[j].vis) trie[j].vis=1,j=trie[j].fail;
}
}
int find(char s[])
{
int p=0,len=strlen(s),ans=0;
for(int i=0;i<len;i++)
{
p=trie[p].son[val(s[i])];
if(trie[p].vis) ans=i+1;
}
return ans;
}
signed main()
{
read(n,m); scanf("%s",t);
for(int i=1;i<=m;i++) scanf("%s",s[i]),insert(s[i]);
build(),ask();
for(int i=1;i<=m;i++) write(find(s[i])),puts("");
}
with 环
P2444 [POI2000] 病毒
分析题意，若在 AC 自动机上存在一个以根节点为起点的环且其中不存在病毒串则合法，那么 fail 树的作用就是让 \(p\) 继承 \(fail(p)\) 的状态表示是否匹配病毒。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define risk(p) trie[p].risk
#define vis(p) trie[p].vis
#define yet(p) trie[p].yet
using namespace std;
const int N=3e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,tot;
struct aa {int son[2],fail; bool risk,vis,yet;}trie[N];
void insert(char s[])
{
int p=0,len=strlen(s);
for(int i=0,c;i<len;i++)
{
c=s[i]-'0';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
risk(p)=1;
}
void build()
{
queue<int>q;
for(int i=0;i<=1;i++) if(son(0,i))
q.push(son(0,i));
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0,y,z;i<=1;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
risk(y)|=risk(fail(y));
q.push(y);
}
}
}
bool dfs(int x)
{
vis(x)=yet(x)=1;
for(int i=0,y;i<=1;i++)
{
y=son(x,i);
if(vis(y)) return 1;
if(risk(y)||yet(y)) continue;
if(dfs(y)) return 1;
}
vis(x)=0;
return 0;
}
signed main()
{
read(n); char s[N];
for(int i=1;i<=n;i++) scanf("%s",s),insert(s);
build();
puts(dfs(0)?"TAK":"NIE");
}
with 栈
P3121 [USACO15FEB] Censoring G
匹配的时候每个节点找到他 fail 树上深度最小的非 \(0\) 的祖先，若他处于某个模式串的结尾状态就删掉，那么这个删掉与插入的操作可以通过栈来实现，找祖先的操作肯定不能暴力跳，直接记录一下就好。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define len(p) trie[p].len
#define to(p) trie[p].to
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,tot,top,cnt,pos[N],tmp[N];
char s[N],t[N],sta[N];
struct aa {int son[26],fail,len,to=-1;}trie[N];
void insert(char s[])
{
int p=0,len=strlen(s);
for(int i=0,c;i<len;i++)
{
c=s[i]-'a';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
len(p)=len;
}
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 x=q.front(); q.pop();
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
q.push(y);
}
}
}
void ask(char s[])
{
int p=0,len=strlen(s);
for(int i=0,j;i<len;i++)
{
sta[++top]=s[i];
j=p=son(p,s[i]-'a');
if(to(j)!=-1) j=to(p);
else
{
for(;j&&!len(j);j=to(j)?to(j):fail(j)) tmp[++cnt]=j;
for(int i=1;i<=cnt;i++) to(tmp[i])=j;
cnt=0;
}
if(len(j)) p=pos[top-=len(p)];
else pos[top]=p;
}
}
signed main()
{
scanf("%s",t),read(n);
for(int i=1;i<=n;i++) scanf("%s",s),insert(s);
build(),ask(t);
for(int i=1;i<=top;i++) putchar(sta[i]);
}
with 朴素 DP
P3041 [USACO12JAN] Video Game G
相当板的 AC 自动机优化 DP，把 AC 自动机建出来，设 \(f_{i,j}\) 表示处理到第 \(i\) 位，当前处于 AC 自动机上的节点 \(j\) 时的最大值。那么显然有转移：
\[f_{i,son_p}=\max(f_{i,son_p},f_{i-1,p}+end_{son_p}) \]最终答案为 \(\max\limits_{i=0}^{tot}\{f_{k,i}\}\)，fail 树的作用时继承 \(end\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define end(p) trie[p].end
using namespace std;
const int N=25;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tot,ans,f[2][N*N];
struct aa {int son[3],fail,end;}trie[N*N];
void insert(char s[])
{
int p=0;
for(int i=0,c;s[i];i++)
{
c=s[i]-'A';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
end(p)++;
}
void build()
{
queue<int>q;
for(int i=0;i<3;i++) if(son(0,i)) q.push(son(0,i));
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0,y,z;i<3;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
end(y)+=end(fail(y));
q.push(y);
}
}
}
signed main()
{
read(n,m); char s[N];
for(int i=1;i<=n;i++) scanf("%s",s),insert(s);
build(); memset(f,128,sizeof(f)),f[0][0]=0;
for(int i=1;i<=m;i++)
{
memset(f[i&1],128,4*(tot+1));
for(int p=0;p<=tot;p++)
for(int c=0,y=son(p,0);c<3;c++,y=son(p,c))
f[i&1][y]=max(f[i&1][y],f[(i-1)&1][p]+end(y));
}
for(int i=0;i<=tot;i++) ans=max(ans,f[m&1][i]);
write(ans);
}
P4052 [JSOI2007] 文本生成器
一样的板题，\(f_{i,j}\) 表示处理到第 \(i\) 为，当前处于 AC 自动机上节点 \(j\) 时满足不匹配任何模式串的方案数，有：
\[f_{i,son_p}+=f_{i-1,p}\times [end_{son_p}=0] \]最后答案为 \(26^n-\sum\limits_{i=0}^{tot}f_{m,i}\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define end(p) trie[p].end
using namespace std;
const int N=6010,P=1e4+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tot,ans=1,f[2][N];
struct aa {int son[26],fail; bool end;}trie[N];
void insert(char s[])
{
int p=0,len=strlen(s);
for(int i=0,c;i<len;i++)
{
c=s[i]-'A';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
end(p)=1;
}
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 x=q.front(); q.pop();
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
end(y)|=end(fail(y));
q.push(y);
}
}
}
signed main()
{
read(n,m); char s[N];
for(int i=1;i<=n;i++) scanf("%s",s),insert(s);
build(); f[0][0]=1;
for(int i=1;i<=m;i++)
{
memset(f[i&1],0,4*(tot+1));
for(int p=0;p<=tot;p++)
for(int c=0;c<26;c++) if(!end(son(p,c)))
(f[i&1][son(p,c)]+=f[(i-1)&1][p])%=P;
}
for(int i=1;i<=m;i++) (ans*=26)%=P;
for(int i=0;i<=tot;i++) (ans+=P-f[m&1][i])%=P;
write(ans);
}
with 状压
P2322 [HNOI2006] 最短母串问题
\(n\) 很小考虑状压，AC 自动机上跑 bfs 同时记录状态，当状态满了的时候直接输出即可，因为是 bfs 所以一定是最短且字典序最小，fail 树依然是继承状态，需要一个 \(vis\) 记录当前状态是否跑过防止死循环。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define id(p) trie[p].id
using namespace std;
const int L=55,N=610,S=4100,M=2.5e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tot,now,last[M];
char s[L],t[M],ans[M];
bitset<S>vis[N];
struct aa {int son[26],fail,id;}trie[N];
void insert(char s[],int id)
{
int p=0,len=strlen(s);
for(int i=0,c;i<len;i++)
{
c=s[i]-'A';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
id(p)|=id;
}
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 x=q.front(); q.pop();
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
id(y)|=id(fail(y));
q.push(y);
}
}
}
void ask(char s[],char ans[])
{
queue<pair<int,int> >q;
q.push(make_pair(0,0)),vis[0].set(0);
for(tot=now=0;!q.empty();now++)
{
int x=q.front().first,sta=q.front().second; q.pop();
if(sta==(1<<n)-1)
{
for(;now;now=last[now]) ans[++m]=s[now];
return ;
}
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=id(y);
if(vis[y][sta|z]) continue;
vis[y].set(sta|z);
q.push(make_pair(y,sta|z));
last[++tot]=now;
s[tot]=i+'A';
}
}
}
signed main()
{
read(n);
for(int i=1;i<=n;i++) scanf("%s",s),insert(s,1<<(i-1));
build(),ask(t,ans);
for(int i=m;i>=1;i--) putchar(ans[i]);
}
类似题目 [ABC343G] Compress Strings&CF25E Test
（和 AC 自动机无关）只需要求长度但 \(vis\) 开不下。
若 \(n\) 很小直接 kmp 然后对于，每对 \((i,j)\) 处理出 \(pub_{i,j}\) 表示 \(s_j\) 前缀匹配 \(s_i\) 后缀最大长度然后暴力美剧拼起来即可。
若 \(n!\) 不能接受呢？考虑状压 DP，\(f_{i,s}\) 表示以 \(i\) 结尾，状态为 \(s\) 时的最小长度，照着上面直接转移即可，注意特殊处理一个串被另一个串包含的情况。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define id(p) trie[p].id
using namespace std;
const int N=21,M=2e5+10,S=1.1e6;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,ans=0x3f3f3f3f,maxx,len[N],nxt[M],pub[N][N],f[S][N];
string s[N];
bool vis[N];
bool check(int x,int y)
{
string t1=" "+s[x],t2=" "+s[y];
for(int i=2,j=0;i<=len[y];i++)
{
while(j&&t2[j+1]!=t2[i]) j=nxt[j];
if(t2[i]==t2[j+1]) j++;
nxt[i]=j;
}
for(int i=1,j=0;i<=len[x];i++)
{
while(j&&t2[j+1]!=t1[i]) j=nxt[j];
if(t1[i]==t2[j+1]) j++;
if(j==len[y]&&i!=len[x]) return 0;
}
return 1;
}
int solve(int x,int y)
{
string t=" "+s[y]+s[x];
int m=t.size()-1,mx=min(len[x],len[y]);
for(int i=2,j=0;i<=m;i++)
{
while(j&&t[j+1]!=t[i]) j=nxt[j];
if(t[j+1]==t[i]) j++;
nxt[i]=j;
}
while(nxt[m]>mx) m=nxt[m];
return nxt[m];
}
signed main()
{
read(n);
for(int i=1;i<=n;i++) cin>>s[i],len[i]=s[i].size();
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j)
check(i,j)?pub[i][j]=solve(i,j):vis[j]=1;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) if(!vis[i]) f[1<<(i-1)][i]=len[i];
for(int i=1;i<=n;i++) if(!vis[i]) maxx|=(1<<(i-1));
for(int s=0;s<=maxx;s++)
for(int i=1;i<=n;i++) if(!((s>>(i-1))&1)&&!vis[i])
for(int j=1;j<=n;j++) if((s>>(j-1))&1&&!vis[j])
f[s|(1<<(i-1))][i]=min(f[s|(1<<(i-1))][i],f[s][j]+len[i]-pub[j][i]);
for(int i=1;i<=n;i++) if(!vis[i]) ans=min(ans,f[maxx][i]);
write(ans);
}
P4045 [JSOI2009] 密码
AC 自动机上跑 DP，和上面那个是类似的只是搬到 AC 自动机上而已，考虑若给定长度大于理论最小值，那么其方案数一定大于 \(42\)，所以若答案小于 \(42\) AC 自动机上跑 dfs 即可，这样出来的一定按照字典序排好，需要注意的是 dfs 时 \(fail(p)\) 跑过的 \(p\) 可能再跑一遍。
或者说因为 \(n!\) 也可以接受，dfs 可以考虑换成全排列暴力，不过会慢很多。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define end(p) trie[p].end
using namespace std;
const int N=15,Q=50,M=110,S=1030;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,mx,tot,len[N];
ll f[2][S][M],ans;
char s[N][N],t[M];
bitset<S>vis[M][M],reach[M][M];
struct aa {int son[26],fail,end;}trie[M];
void insert(char s[],int id)
{
int p=0;
for(int i=0,c;i<len[id];i++)
{
c=s[i]-'a';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
end(p)|=1<<(id-1);
}
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 x=q.front(); q.pop();
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
end(y)|=end(fail(y));
q.push(y);
}
}
}
void dfs(int p,int vlen,int sta)
{
if(vlen==m)
{
if(sta!=mx) return ;
reach[p][vlen].set(sta);
for(int i=1;i<=m;i++) putchar(t[i]);
puts(""); return ;
}
for(int c=0,y,tmp;c<26;c++) if((y=son(p,c))!=0)
if(!vis[y][vlen+1][tmp=sta|end(y)]||reach[y][vlen+1][tmp])
{
vis[y][vlen+1].set(tmp);
t[vlen+1]=c+'a';
dfs(y,vlen+1,tmp);
if(reach[y][vlen+1][tmp]) reach[p][vlen].set(sta);
}
}
signed main()
{
read(m,n),mx=(1<<n)-1;
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]),len[i]=strlen(s[i]);
insert(s[i],i);
}
build(); f[0][0][0]=1;
for(int i=1;i<=m;i++)
{
memset(f[i&1],0,sizeof(f[i&1]));
for(int s=0;s<=mx;s++)
for(int p=0;p<=tot;p++) if(f[(i-1)&1][s][p])
{
ll tmp=f[(i-1)&1][s][p];
for(int c=0;c<26;c++)
f[i&1][s|end(son(p,c))][son(p,c)]+=tmp;
}
}
for(int i=0;i<=tot;i++) ans+=f[m&1][mx][i];
write(ans),puts(""); if(ans>42) return 0;
dfs(0,0,0);
}
with dfs 序
这种情况通常套个数据结构或树上结构。
P2414 [NOI2011] 阿狸的打字机
和那次模拟赛的题一样不用每个串都单独插入一遍。
建完 AC 自动机后跑一遍 fail 树上的 dfs 序，那么对于一个点会对他的子树上所有节点造成贡献，由此树状数组维护一下就好了，加入一个字符将对应 \(dfn\) 权值 \(+1\)，回溯就 \(-1\)，这样树状数组存的就是当前字符串，那么询问离线下来，遇到一个 P 就处理 \(x\) 等于当前点的所有询问，也就是查他子树的权值和。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int m,ed[N],ans[N];
char s[N];
vector<pair<int,int> >g[N];
struct ACM
{
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define fa(p) trie[p].fa
#define in(p) trie[p].in
#define out(p) trie[p].out
int tot;
struct aa {int son[26],fail,fa,in,out;}trie[N];
vector<int>e[N];
void insert(int &p,int c)
{
if(!son(p,c)) son(p,c)=++tot,fa(son(p,c))=p;
p=son(p,c);
}
void remove(int &p) {p=fa(p);}
void build()
{
queue<int>q; tot=0;
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();
e[fail(x)].push_back(x);
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
q.push(y);
}
}
}
void dfs(int x)
{
in(x)=++tot;
for(int y:e[x]) dfs(y);
out(x)=tot;
}
}A;
struct BIT
{
#define lowbit(x) (x&-x)
int c[N],mx;
void change(int x,int d) {for(;x<=mx;x+=lowbit(x)) c[x]+=d;}
int ask(int x)
{
int res=0;
for(;x;x-=lowbit(x)) res+=c[x];
return res;
}
}B;
signed main()
{
scanf("%s",s),read(m); int len=strlen(s);
for(int i=0,n=0,p=0;i<len;i++)
{
if(s[i]=='P') ed[++n]=p;
else if(s[i]=='B') A.remove(p);
else A.insert(p,s[i]-'a');
}
A.build(),A.dfs(0),B.mx=A.tot;
for(int i=1,x,y;i<=m;i++)
read(x,y),g[y].push_back(make_pair(x,i));
for(int i=0,n=0,p=0;i<len;i++)
{
if(s[i]=='P') for(auto pos:g[++n])
ans[pos.second]=B.ask(A.out(ed[pos.first]))-B.ask(A.in(ed[pos.first])-1);
else if(s[i]=='B') B.change(A.in(p),-1),p=A.fa(p);
else p=A.son(p,s[i]-'a'),B.change(A.in(p),1);
}
for(int i=1;i<=m;i++) write(ans[i]),puts("");
}
P5840 [COCI2015] Divljak
与上面题目类似不过不用离线了，但是这个每个串对答案贡献都不能重复计算，那么可以通过树上差分将“路径加、单点求值”转换为“单点加、子树求和”，只需要对于插入一个串，其每个节点对应 fail 树上 dfs 序从小到大排好序，树状数组上每个 \(dfn_i\) 进行 \(+1\)，每个 \(lca(dfn_{i-1},dfn_i)\) 进行 \(-1\)，查询依旧是子树求和。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,M=2e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,ed[N];
char s[M];
struct BIT
{
#define lowbit(x) (x&-x)
int c[M],mx;
void add(int x) {for(;x<=mx;x+=lowbit(x)) c[x]++;}
void del(int x) {for(;x<=mx;x+=lowbit(x)) c[x]--;}
int ask(int x)
{
int res=0;
for(;x;x-=lowbit(x)) res+=c[x];
return res;
}
}B;
struct ACM
{
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
int tot,fa[M],sz[M],son[M],dfn[M],dep[M],top[M],tmp[M];
vector<int>e[M];
struct aa {int son[26],fail;}trie[M];
void insert(char s[],int id)
{
int p=0;
for(int i=0,c;s[i];i++)
{
c=s[i]-'a';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
ed[id]=p;
}
void build()
{
queue<int>q; memset(son,-1,4*(tot+1)),tot=0;
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();
e[fail(x)].push_back(x);
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
q.push(y);
}
}
}
void dfs1(int x,int t)
{
fa[x]=t,sz[x]=1,dfn[x]=++tot,dep[x]=dep[t]+1;
for(int y:e[x])
{
dfs1(y,x);
sz[x]+=sz[y];
son[x]=son[x]==-1?y:(sz[y]>sz[son[x]]?y:son[x]);
}
}
void dfs2(int x,int t)
{
top[x]=t;
if(son[x]) dfs2(son[x],t);
for(int y:e[x]) if(y!=son[x]) dfs2(y,y);
}
int lca(int x,int y)
{
for(;top[x]!=top[y];x=fa[top[x]])
if(dep[top[x]]<dep[top[y]]) swap(x,y);
return dep[x]<dep[y]?x:y;
}
void solve(char s[])
{
int p=0,len=0;
for(int i=0;s[i];i++) p=son(p,s[i]-'a'),tmp[++len]=p;
sort(tmp+1,tmp+1+len,[=](int x,int y){return dfn[x]<dfn[y];});
len=unique(tmp+1,tmp+1+len)-(tmp+1);
for(int i=1;i<=len;i++) B.add(dfn[tmp[i]]);
for(int i=2;i<=len;i++) B.del(dfn[lca(tmp[i],tmp[i-1])]);
}
}A;
signed main()
{
read(n);
for(int i=1;i<=n;i++) scanf("%s",s),A.insert(s,i);
B.mx=A.tot+1,A.build(),A.dfs1(0,B.mx+1),A.dfs2(0,0);
cin>>n;
for(int i=1,op,x;i<=n;i++)
{
cin>>op;
if(op==1) scanf("%s",s),A.solve(s);
else
{
read(x),x=ed[x];
write(B.ask(A.dfn[x]+A.sz[x]-1)-B.ask(A.dfn[x]-1)),puts("");
}
}
}
BZOJ2095 背单词
某种意义上是最长上升子序列，那么对于串 \(s_i\) 每个字符在 fail 树上的所有祖先中 DP 值取 \(\max\) 再加上 \(w_i\) 就是 \(end_i\) 的 DP 值，\(end_i\) 指 \(s_i\) 的结尾对应自动机上的节点，发现又是一个“路径求 \(\max\)，单点赋值”的问题，可以通过 dfs 序转化为“子树赋值，单点求 \(\max\)” 问题，即一个点会对 fail 树上其子树的所有节点产生贡献，由此线段树维护一下就好。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e4+10,M=3e5+10;
int test,n,ans,w[N];
string s[N];
struct TREE
{
#define f t[p]
#define ls p<<1
#define rs p<<1|1
struct aa {int val,lazy;}t[M<<2];
void build(int p,int l,int r)
{
f.val=f.lazy=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
}
void spread(int p)
{
int &v=f.lazy;
if(!v) return ;
t[ls].val=max(t[ls].val,v),t[ls].lazy=max(t[ls].lazy,v);
t[rs].val=max(t[rs].val,v),t[rs].lazy=max(t[rs].lazy,v);
v=0;
}
void change(int p,int l,int r,int vl,int vr,int d)
{
if(vl<=l&&vr>=r)
{
f.val=max(f.val,d),f.lazy=max(f.lazy,d);
return ;
}
spread(p); int mid=(l+r)>>1;
if(vl<=mid) change(ls,l,mid,vl,vr,d);
if(vr>mid) change(rs,mid+1,r,vl,vr,d);
f.val=max(t[ls].val,t[rs].val);
}
int ask(int p,int l,int r,int x)
{
if(l==r) return f.val;
spread(p); int mid=(l+r)>>1;
return (x<=mid)?ask(ls,l,mid,x):ask(rs,mid+1,r,x);
}
}T;
struct ACM
{
#define son(p,c) trie[p].son[c]
#define fail(p) trie[p].fail
#define in(p) trie[p].in
#define out(p) trie[p].out
int tot,ed[N]; vector<int>e[M];
struct aa
{
int son[26],fail,in,out;
void clean() {memset(son,0,4*27),fail=in=out=0;}
}trie[M];
void clean()
{
for(int i=0;i<=tot;i++) trie[i].clean();
for(int i=0;i<=tot;i++) vector<int>().swap(e[i]);
memset(ed,0,4*(n+1)),tot=0;
}
void insert(string &s,int id)
{
int p=0,len=s.size();
for(int i=0,c;i<len;i++)
{
c=s[i]-'a';
if(!son(p,c)) son(p,c)=++tot;
p=son(p,c);
}
ed[id]=p;
}
void build()
{
queue<int>q; tot=0;
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();
e[fail(x)].push_back(x);
for(int i=0,y,z;i<26;i++)
{
y=son(x,i),z=fail(x);
if(!y) {son(x,i)=son(z,i); continue;}
fail(y)=son(z,i);
q.push(y);
}
}
}
void dfs(int x)
{
in(x)=++tot;
for(int y:e[x]) dfs(y);
out(x)=tot;
}
void solve(string &s,int id)
{
int p=0,len=s.size(),res=0;
for(int i=0;i<len;i++)
{
p=son(p,s[i]-'a');
res=max(res,T.ask(1,1,tot,in(p)));
}
res+=w[id],ans=max(ans,res);
T.change(1,1,tot,in(ed[id]),out(ed[id]),res);
}
}A;
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>test;
while(test--)
{
cin>>n; A.clean(),ans=0;
for(int i=1;i<=n;i++)
{
cin>>s[i]>>w[i];
if(w[i]>0) A.insert(s[i],i);
}
A.build(),A.dfs(0),T.build(1,1,A.tot);
for(int i=1;i<=n;i++) if(w[i]>0) A.solve(s[i],i);
cout<<ans<<endl;
}
}
with 矩阵快速幂
P4569 [BJWC2011] 禁忌
贪心的角度，从前往后扫，一旦可以分割立刻分隔，从而使结果最大。
fail 树用来继承状态，先考虑朴素 DP 怎么做，\(f_{i,p}\) 表示处理到第 \(i\) 位，当前处于 AC 自动机上节点 \(p\) 时的概率，按照上面的贪心，有：
\[\begin{cases} f_{i,j}=\frac{1}{alphabet}\sum_{j\in son_k}f_{i-1,k} &end_j=0\\ f_{i,0}=\frac{1}{alphabet}\sum_{j=0}^{tot}\sum_{j\in son_k}f_{i-1,k} &end_j=1\\ \end{cases} \]对于每一个点 \(p\) 且 \(end_p=1\) 会有 \(\sum\limits_{i=1}^nf_{i,p}\) 概率产生 \(1\) 的贡献，所以有：
\[ans=\sum_{i=1}^n\sum_{j=0}^{tot}[end_j=1]f_{i,j} \]这是暴力，发现 \(n\) 太大无法接受，而 \(tot\) 却很小可以接受 \(tot^3\)，所以与 P3193 [HNOI2008] GT考试 这题一样的矩阵快速幂优化一下就好了，搞一个节点 \(tot+1\) 用来统计答案。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=25;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,P,anss,nxt[N],a[N][N],c[N][N],ans[N][N];
char s[N];
void qpow(int b)
{
for(int i=1;i<=m;i++) ans[i][i]=1;
for(;b;b>>=1)
{
if(b&1)
{
for(int i=1;i<=m;i++) for(int k=1;k<=m;k++)
for(int j=1,tmp=a[i][k];j<=m;j++)
(c[i][j]+=ans[k][j]*tmp%P)%=P;
for(int i=1;i<=m;i++) for(int j=1;j<=m;j++)
ans[i][j]=c[i][j],c[i][j]=0;
}
for(int i=1;i<=m;i++) for(int k=1;k<=m;k++)
for(int j=1,tmp=a[i][k];j<=m;j++)
(c[i][j]+=a[k][j]*tmp%P)%=P;
for(int i=1;i<=m;i++) for(int j=1;j<=m;j++)
a[i][j]=c[i][j],c[i][j]=0;
}
}
signed main()
{
read(n,m,P),scanf("%s",s+1);
for(int i=2,j=0;i<=m;i++)
{
while(j&&s[j+1]!=s[i]) j=nxt[j];
if(s[j+1]==s[i]) j++;
nxt[i]=j;
}
for(int i=0;i<=m-1;i++) for(int j='0',k;j<='9';j++)
{
for(k=i;k&&s[k+1]!=j;k=nxt[k]);
k+=(s[k+1]==j);
(a[i+1][k+1]+=(k<=m-1))%=P;
}
qpow(n); memset(a[1],0,sizeof(a[1])),a[1][1]=1;
for(int k=1;k<=m;k++) for(int j=1,tmp=a[1][k];j<=m;j++)
c[1][j]+=ans[k][j]*tmp;
for(int i=1;i<=m;i++) (anss+=c[1][i])%=P;
write(anss);
}