【學習筆記】AC自動機
AC自動機是以trie結構為基礎，結合KMP算法思想構建的，用于解決多模式串匹配問題。
它的構建方式分為以下幾步：
\(1.\) 建立trie樹
\(2.\) 構建失配（fail）指針
其中 fail 指針指向的是當前節點的狀態的后綴所對應的狀態。
這里明確一下，trie樹中的每個節點表示的是一個狀態，及某個模式串的前綴。
因此若這個狀態可以在文本串中匹配，則它的后綴必定也能在文本串中匹配。
構建 fail 指針的過程是一個 bfs，對于每個點，用其父親的 fail 來更新自己的 fail。
即，父親的后綴加上自己當前的這一位字符，就是自己的后綴了。
核心代碼：
for(int i=0;i<=25;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=25;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}
else{ // 重構trie樹結構
tr[u][i]=tr[fail[u]][i];
}
}
}
代碼中有一點是沒有提到的，就是加了注釋的那一句。即，若沒有 u+(i+'a') 這個狀態，就讓這個狀態指向這個狀態的后綴。于是在前面那句 if 和以后的匹配中，可以避免 while 循環不停跳 fail 的情況。
板子題：HDU 2222
匹配時不斷跳 fail 就行了，即若這個狀態能匹配，則它的后綴也能匹配。注意打標記避免重復匹配，否則時間復雜度無法保證。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e4+5,maxm=1e6+5;
int T,n,tot,tr[maxn*50][30];
int fail[maxn*50],end[maxn*50];
char s[maxm];
queue<int> q;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(T);
while(T--){
tot=0;
fail[0]=end[0]=0;
for(int i=0;i<=25;i++){
tr[0][i]=0;
}
read(n);
while(n--){
scanf(" %s",s+1);
int len=strlen(s+1);
int p=0;
for(int i=1;i<=len;i++){
int d=s[i]-'a';
if(!tr[p][d]){
tr[p][d]=++tot;
fail[tot]=end[tot]=0;
for(int j=0;j<=25;j++){
tr[tot][j]=0;
}
}
p=tr[p][d];
}
end[p]++;
}
for(int i=0;i<=25;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=25;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
scanf(" %s",s+1);
n=strlen(s+1);
int res=0,p=0;
for(int i=1;i<=n;i++){
p=tr[p][s[i]-'a'];
for(int j=p;j&&~end[j];j=fail[j]){
res+=end[j];
end[j]=-1;
}
}
printf("%d\n",res);
}
return 0;
}
}
int main(){return asbt::main();}
Luogu P5231
這里就要注意到，trie樹上本來的從父親連向兒子的邊，和構建 fail 指針時為了方便重構的邊的區別了。在代碼中，后者用 \(tra\) 表示。
每個點都是它的子節點的前綴，于是可以將父親節點的答案（如果有的話）傳給兒子節點，最后在葉子節點統計答案即可。因為是動態開點，每個點的子節點編號肯定比它自己大，因此不用 dfs 遍歷整棵樹，直接順序遍歷所有節點就可以了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define mp make_pair
#define lwrb lower_bound
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e7+5,maxm=1e5+5;
int n,m,tot,tr[maxn][4],fail[maxn];
int dep[maxn],zhi[maxn],ans[maxm];
int tra[maxn][4];
char s[maxn],t[105];
multimap<int,int> hao;
queue<int> q;
il int gid(char x){
if(x=='E'){
return 0;
}
if(x=='S'){
return 1;
}
if(x=='W'){
return 2;
}
return 3;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
scanf(" %s",s+1);
for(int i=1;i<=m;i++){
scanf(" %s",t+1);
int p=0,len=strlen(t+1);
for(int j=1;j<=len;j++){
int d=gid(t[j]);
if(!tr[p][d]){
tra[p][d]=tr[p][d]=++tot;
}
p=tr[p][d];
dep[p]=j;
}
hao.insert(mp(p,i));
}
for(int i=0;i<=3;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=3;i++){
if(tr[u][i]){
fail[tr[u][i]]=tra[fail[u]][i];
q.push(tr[u][i]);
}
else{
tra[u][i]=tra[fail[u]][i];
}
}
}
int p=0;
for(int i=1;i<=n;i++){
p=tra[p][gid(s[i])];
for(int j=p;j&&!zhi[j];j=fail[j]){
zhi[j]=dep[j];
}
}
for(int i=1;i<=tot;i++){
bool flag=0;
for(int j=0;j<=3;j++){
if(tr[i][j]){
flag=1;
zhi[tr[i][j]]=max(zhi[tr[i][j]],zhi[i]);
}
}
if(!flag){
auto l=hao.lwrb(i);
auto r=hao.uprb(i);
while(l!=r){
ans[l++->second]=zhi[i];
}
}
}
for(int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
}
int main(){return asbt::main();}
然后我突然發現了一個問題，如果有一個模式串是另一個模式串的前綴的話，那它的結尾就不是葉子節點，就會無法統計到答案。比如下面這組數據：
4 2
NNSS
NN
NNS
剛才這篇代碼會對第一個模式串輸出 0。因此需要在每個節點記一個 end，然后把統計答案的判斷條件改為 end[i]。（為什么不在每個節點都統計一遍答案呢，因為時間會達到 \(O(n\log m)\)，有可能會炸。）然而洛谷上顯然并沒有這樣的數據。
真正正確的代碼：
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define mp make_pair
#define lwrb lower_bound
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e7+5,maxm=1e5+5;
int n,m,tot,tr[maxn][4],fail[maxn];
int dep[maxn],zhi[maxn],ans[maxm];
int tra[maxn][4];
char s[maxn],t[105];
multimap<int,int> hao;
queue<int> q;
bitset<maxn> end;
il int gid(char x){
if(x=='E'){
return 0;
}
if(x=='S'){
return 1;
}
if(x=='W'){
return 2;
}
return 3;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
scanf(" %s",s+1);
for(int i=1;i<=m;i++){
scanf(" %s",t+1);
int p=0,len=strlen(t+1);
for(int j=1;j<=len;j++){
int d=gid(t[j]);
if(!tr[p][d]){
tra[p][d]=tr[p][d]=++tot;
}
p=tr[p][d];
dep[p]=j;
}
end[p]=1;
hao.insert(mp(p,i));
}
for(int i=0;i<=3;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=3;i++){
if(tr[u][i]){
fail[tr[u][i]]=tra[fail[u]][i];
q.push(tr[u][i]);
}
else{
tra[u][i]=tra[fail[u]][i];
}
}
}
int p=0;
for(int i=1;i<=n;i++){
p=tra[p][gid(s[i])];
for(int j=p;j&&!zhi[j];j=fail[j]){
zhi[j]=dep[j];
}
}
for(int i=1;i<=tot;i++){
for(int j=0;j<=3;j++){
if(tr[i][j]){
zhi[tr[i][j]]=max(zhi[tr[i][j]],zhi[i]);
}
}
if(end[i]){
auto l=hao.lwrb(i);
auto r=hao.uprb(i);
while(l!=r){
ans[l++->second]=zhi[i];
}
}
}
for(int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
}
int main(){return asbt::main();}
/*
4 2
NNSS
NN
NNS
*/
一本通 1482
計算出現次數，那也不難。只需給匹配到的每個點的出現次數都加一，最后對于每個模式串對應到字典樹上的編號查詢即可。這樣做的復雜度是 \(O(n|S|)\) 的，過不去。于是考慮只給 fail 鏈的鏈頭加上貢獻，再跑一遍拓撲排序即可。（因為 fail 指針連成的鏈不可能有環。）
另外，上面那道題用 multimap 存儲字典樹的節點對應的模式串編號的方式非常的蠢，直接開個數組存每個模式串對應的節點編號就行了。否則在一本通上會喜提RE+WA。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5;
int n,len[205],fail[maxn],num[maxn];
int tot,tr[maxn][30],deg[maxn],hao[205];
string s[205];
queue<int> q;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
len[i]=s[i].size();
s[i]=" "+s[i];
int p=0;
for(int j=1;j<=len[i];j++){
int d=s[i][j]-'a';
if(!tr[p][d]){
tr[p][d]=++tot;
}
p=tr[p][d];
}
hao[i]=p;
}
for(int i=0;i<=25;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=25;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
if(fail[tr[u][i]]){
deg[fail[tr[u][i]]]++;
}
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
for(int i=1;i<=n;i++){
int p=0;
for(int j=1;j<=len[i];j++){
p=tr[p][s[i][j]-'a'];
num[p]++;
}
}
for(int i=1;i<=tot;i++){
if(!deg[i]){
q.push(i);
}
}
while(q.size()){
int u=q.front();
q.pop();
int v=fail[u];
if(!v){
continue;
}
num[v]+=num[u];
if(--deg[v]==0){
q.push(v);
}
}
for(int i=1;i<=n;i++){
cout<<num[hao[i]]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
Luogu P2444
題目意思是要找到一個無法匹配任何模式串的無限長的文本串。
不難發現，這樣的串在AC自動機上匹配時會跑出一個環。
因此只需要在AC自動機上找有沒有不經過任何模式串的結尾節點的環就可以了。
但是這里會有問題：某個點或許不是模式串的結尾，但是它的后綴有可能是。
于是在求 fail 時，如果這個點的 fail 是結尾節點，那么就把它也設為結尾節點（dfs時不能經過它）。
代碼不難寫，但會TLE。
原因是由于要找環，在遍歷完這個點的子樹后就將這個點的訪問狀態（vis2 數組）改成0了，但在之后再遍歷這個點是沒有意義的。
因此就再記一個 vis1 數組，記錄是否遍歷過它就行了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=3e4+5;
int n,tot,tr[maxn][2],fail[maxn];
char s[maxn];
bitset<maxn> end,vis1,vis2;
queue<int> q;
il void dfs(int u){
vis1[u]=vis2[u]=1;
for(int i=0;i<=1;i++){
if(vis2[tr[u][i]]){
puts("TAK");
exit(0);
}
if(end[tr[u][i]]||vis1[tr[u][i]]){
continue;
}
dfs(tr[u][i]);
}
vis2[u]=0;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
while(n--){
scanf(" %s",s+1);
int len=strlen(s+1),p=0;
for(int i=1;i<=len;i++){
int d=s[i]&15;
if(!tr[p][d]){
tr[p][d]=++tot;
}
p=tr[p][d];
}
end[p]=1;
}
for(int i=0;i<=1;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=1;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
if(end[fail[tr[u][i]]]){
end[tr[u][i]]=1;
}
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
// for(int i=1;i<=tot;i++){
// cout<<tr[i][0]<<" "<<tr[i][1]<<" "<<fail[i]<<"\n";
// }
dfs(0);
puts("NIE");
return 0;
}
}
int main(){return asbt::main();}
[HNOI2006] 最短母串問題
要求字典序最小，考慮一位一位貪心，bfs。先建出 AC 自動機，然后 bfs 同時記錄路徑即可。需要狀壓。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=605,maxm=(1<<12)+5;
int n,tr[maxn][30],tot;
int fail[maxn],sta[maxn];
pair<pii,int> pre[maxn][maxm];
bool vis[maxn][maxm];
char ans[maxn];
string s;
queue<int> q;
queue<pii> q2;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// cout<<cplx::usdmem();
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,p;i<=n;i++){
cin>>s;
p=0;
for(int j=0,d;j<s.size();j++){
d=s[j]-'A';
if(!tr[p][d]){
tr[p][d]=++tot;
}
p=tr[p][d];
}
sta[p]|=1<<(i-1);
}
for(int i=0;i<=25;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=25;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
sta[tr[u][i]]|=sta[fail[tr[u][i]]];
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
vis[0][0]=1,q2.push(mp(0,0));
// puts("666");
while(q2.size()){
int u=q2.front().fir,S=q2.front().sec;
// puts("666");
// cout<<u<<"\n";
q2.pop();
// puts("777");
if(S==((1<<n)-1)){
int cnt=0;
while(u){
// puts("666");
// cout<<u<<"\n";
ans[++cnt]='A'+pre[u][S].sec;
pii tmp=pre[u][S].fir;
u=tmp.fir,S=tmp.sec;
}
for(int i=cnt;i;i--){
cout<<ans[i];
}
return 0;
}
for(int i=0;i<=25;i++){
if(tr[u][i]&&!vis[tr[u][i]][S|sta[tr[u][i]]]){
vis[tr[u][i]][S|sta[tr[u][i]]]=1;
pre[tr[u][i]][S|sta[tr[u][i]]]=mp(mp(u,S),i);
q2.push(mp(tr[u][i],S|sta[tr[u][i]]));
}
}
}
return 0;
}
}
int main(){return asbt::main();}
「一本通 2.4 練習 6」文本生成器
正難則反，設 \(dp_{i,j}\) 表示到 \(i\) 點串長為 \(j\) 的方案數，從父親向兒子轉移即可。注意轉移順序，應該先枚舉 \(i\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=6e3+5,mod=1e4+7;
int n,m,tot,tr[maxn][30];
int fail[maxn],dp[maxn][105];
bool end[maxn];
queue<int> q;
string s;
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*x%mod;
}
y>>=1,x=x*x%mod;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,p;i<=n;i++){
cin>>s;
p=0;
for(int j=0,d;j<s.size();j++){
d=s[j]-'A';
if(!tr[p][d]){
tr[p][d]=++tot;
}
p=tr[p][d];
}
end[p]=1;
}
for(int i=0;i<=25;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=25;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
if(end[fail[tr[u][i]]]){
end[tr[u][i]]=1;
}
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
dp[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<=tot;j++){
for(int k=0;k<=25;k++){
if(!end[tr[j][k]]){
(dp[tr[j][k]][i]+=dp[j][i-1])%=mod;
}
}
}
}
int ans=0;
for(int i=0;i<=tot;i++){
(ans+=dp[i][m])%=mod;
}
cout<<(qpow(26,m)-ans+mod)%mod;
return 0;
}
}
int main(){return asbt::main();}
[BZOJ 2905]背單詞
設 \(dp_i\) 表示前 \(i\) 個字符串的最大答案。則 \(i\) 只能從它的子串轉移。考慮子串本質就是從前面刪幾個字符再從后面刪幾個字符串，具體到 AC 自動機上就是 \(i\) 的某個前綴跳了若干個 fail。于是我們從 \(fail_i\) 向 \(i\) 連邊，這樣就建出了一棵 fail 樹，對于每個前綴去查詢根鏈[1]的最大值，然后再更新。用線段樹維護即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=3e5+5,inf=0x3f3f3f3f;
int T,n,tr[maxn][30];
int dfn[maxn],sz[maxn];
int fail[maxn],hao[maxn];
int fa[maxn],cnt,a[maxn];
vector<int> e[maxn];
string s;
queue<int> q;
il void dfs(int u){
// cout<<u<<"\n";
dfn[u]=++cnt;
sz[u]=1;
for(int v:e[u]){
dfs(v);
sz[u]+=sz[v];
}
}
struct{
int tr[maxn<<2];
il void build(int id,int l,int r){
tr[id]=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il void upd(int id,int L,int R,int l,int r,int v){
if(L>=l&&R<=r){
tr[id]=max(tr[id],v);
return ;
}
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,v);
}
if(r>mid){
upd(rid,mid+1,R,l,r,v);
}
}
il int query(int id,int l,int r,int p){
int res=tr[id];
if(l==r){
return res;
}
int mid=(l+r)>>1;
return max(res,p<=mid?query(lid,l,mid,p):query(rid,mid+1,r,p));
}
}SG;
il void solve(){
cin>>n;
int tot=0;
for(int i=0;i<=25;i++){
tr[0][i]=0;
}
for(int i=1,p;i<=n;i++){
cin>>s>>a[i];
p=0;
for(int j=0,d;j<s.size();j++){
d=s[j]-'a';
if(!tr[p][d]){
tr[p][d]=++tot;
for(int k=0;k<=25;k++){
tr[tot][k]=0;
}
fa[tot]=p;
}
p=tr[p][d];
}
hao[i]=p;
}
for(int i=0;i<=25;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
// cout<<u<<"\n";
q.pop();
for(int i=0;i<=25;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
// cout<<tot<<"\n";
for(int i=1;i<=tot;i++){
e[fail[i]].pb(i);
}
cnt=0;
dfs(0);
// for(int i=0;i<=tot;i++){
// cout<<i<<" "<<dfn[i]<<" "<<sz[i]<<"\n";
// }
SG.build(1,1,cnt);
int ans=0;
for(int i=1,res,p;i<=n;i++){
p=hao[i],res=0;
// cout<<i<<"-\n";
while(p){
// cout<<p<<"\n";
res=max(res,SG.query(1,1,cnt,dfn[p]));
p=fa[p];
}
res=max(res,res+a[i]);
ans=max(ans,res);
SG.upd(1,1,cnt,dfn[hao[i]],dfn[hao[i]]+sz[hao[i]]-1,res);
// cout<<res<<"\n";
}
cout<<ans<<"\n";
for(int i=0;i<=tot;i++){
fa[i]=fail[i]=0;
e[i].clear();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// freopen("433.in","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
[JSOI2009]密碼
設 \(dp_{i,j,S}\) 表示填了 \(i\) 位，在 AC 自動機上的 \(j\) 號節點，當前覆蓋的字符串集位 \(S\) 的方案數。于是有轉移：
\[\large{dp_{i,j,S}\to dp_{i+1,tr_{j,k},S\operatorname{or}sta_{tr_{j,k}}}}
\]
其中 \(tr_{j,k}\) 表示 AC 自動機上 \(j\) 點加上字符 \(k\) 的節點，\(sta_j\) 表示以 \(j\) 點為結尾的字符串構成的集合，\(\operatorname{or}\) 表示按位或。
輸出方案，先記憶化搜索確定每個狀態 \((i,j,S)\) 能否轉移到合法狀態，再一遍 dfs 輸出即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<10)+5;
int n,m,tr[105][30],tot;
int fail[105],sta[105];
ll dp[30][105][maxn];
bool vis[30][105][maxn];
bool f[30][105][maxn];
char ans[maxn];
string s;
queue<int> q;
il bool dfs1(int i,int j,int S){
if(vis[i][j][S]){
return f[i][j][S];
}
vis[i][j][S]=1;
if(i==m){
return f[i][j][S]=S==(1<<n)-1;
}
bool &res=f[i][j][S];
for(int k=0;k<=25;k++){
res|=dfs1(i+1,tr[j][k],S|sta[tr[j][k]]);
}
return res;
}
il void dfs2(int i,int j,int S){
if(i==m){
for(int k=1;k<=m;k++){
cout<<ans[k];
}
cout<<"\n";
return ;
}
for(int k=0;k<=25;k++){
if(f[i+1][tr[j][k]][S|sta[tr[j][k]]]){
ans[i+1]=k+'a';
dfs2(i+1,tr[j][k],S|sta[tr[j][k]]);
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>m>>n;
for(int i=1,p;i<=n;i++){
cin>>s;
p=0;
for(int j=0,d;j<s.size();j++){
d=s[j]-'a';
if(!tr[p][d]){
tr[p][d]=++tot;
}
p=tr[p][d];
}
sta[p]|=1<<(i-1);
}
for(int i=0;i<=25;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<=25;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
sta[tr[u][i]]|=sta[fail[tr[u][i]]];
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
dp[0][0][0]=1;
for(int i=0;i<=m;i++){
for(int j=0;j<=tot;j++){
for(int S=0;S<1<<n;S++){
if(!dp[i][j][S]){
continue;
}
for(int k=0;k<=25;k++){
dp[i+1][tr[j][k]][S|sta[tr[j][k]]]+=dp[i][j][S];
}
}
}
}
ll ans=0;
for(int i=0;i<=tot;i++){
ans+=dp[m][i][(1<<n)-1];
}
cout<<ans<<"\n";
if(ans>42){
return 0;
}
dfs1(0,0,0);
dfs2(0,0,0);
return 0;
}
}
int main(){return asbt::main();}
[bzoj2553]禁忌
考慮如果暴力 DP 的話，時間復雜度會超標，于是矩陣加速。
但是在 DP 的過程中，期望又要乘又要加的，用矩陣很難轉移。于是考慮用矩陣去算概率，新開一行去存期望。
這個貪心是很顯然的：當匹配完了一個單詞時，直接從頭開始嘗試匹配下一個單詞。由于題目要求不能重疊，這不僅是策略上的優化還是正確性的保證。
具體地，假設要從節點 \(j\) 轉移到 \(k\)，如果 \(k\) 是某個單詞的結尾，那就把貢獻加給根，同時加給期望。否則就只能加給 \(k\) 了。
時間復雜度 \(O((\sum|T_i|)^3\log len)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
int n,m,tr[80][30];
int tot,fail[80];
double ab;
bool end[80];
string s;
queue<int> q;
struct juz{
double mat[80][80];
juz(){
for(int i=0;i<=tot;i++){
for(int j=0;j<=tot;j++){
mat[i][j]=0;
}
}
}
il double*operator[](int x){
return mat[x];
}
il juz operator*(juz x)const{
juz res;
for(int i=0;i<=tot;i++){
for(int j=0;j<=tot;j++){
for(int k=0;k<=tot;k++){
res[i][j]+=mat[i][k]*x[k][j];
}
}
}
return res;
}
}bas;
il juz qpow(juz x,int y){
juz res;
for(int i=0;i<=tot;i++){
res[i][i]=1;
}
while(y){
if(y&1){
res=res*x;
}
y>>=1,x=x*x;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>ab;
for(int i=1,p;i<=n;i++){
cin>>s;
p=0;
for(int j=0,d;j<s.size();j++){
d=s[j]-'a';
if(!tr[p][d]){
tr[p][d]=++tot;
}
p=tr[p][d];
}
end[p]=1;
}
for(int i=0;i<ab;i++){
if(tr[0][i]){
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<ab;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
end[tr[u][i]]|=end[fail[tr[u][i]]];
q.push(tr[u][i]);
}
else{
tr[u][i]=tr[fail[u]][i];
}
}
}
// for(int i=0;i<=tot;i++){
// cout<<fail[i]<<" ";
// }
// puts("");
tot++;
for(int i=0;i<tot;i++){
for(int j=0;j<ab;j++){
if(end[tr[i][j]]){
bas[i][0]+=1.0/ab;
bas[i][tot]+=1.0/ab;
}
else{
bas[i][tr[i][j]]+=1.0/ab;
}
}
}
bas[tot][tot]=1;
printf("%.10f",qpow(bas,m)[0][tot]);
return 0;
}
}
int main(){return asbt::main();}
根鏈：由 2024 陜西省隊隊員馬思博提出，指一棵樹上一個端點在樹根的鏈。（摘自 UKE 的題解） ??
浙公網安備 33010602011771號