【字符串】AC自动机+dp

关于cnt

只有这一种

标记危险 cnt[p]=1 cnt[p]|=cnt[ne[p]]

记录个数cnt[p]++; cnt[p]+=cnt[ne[p]]

P3041 [USACO12JAN] Video Game G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
using namespace std;
#include<cstring>
const int M=1010;
const int NODE=15*20+10;
int f[M][NODE];int ne[NODE];int cnt[NODE];
int tr[NODE][3];int idx=0;
int get(char c){
if(c=='A')return 0;
if(c=='B')return 1;
if(c=='C')return 2;
}void insertt(string str){
int p=0;
for(int i=0;str[i];i++){int u=get(str[i]);if(!tr[p][u])tr[p][u]=++idx;p=tr[p][u];
}
cnt[p]++;}void bui(){int q[NODE];
int hh=0;int tt=-1;
for(int i=0;i<3;i++)if(tr[0][i])q[++tt]=tr[0][i];while(hh<=tt){int t=q[hh++];for(int i=0;i<3;i++){int p=tr[t][i];if(!p)tr[t][i]=tr[ne[t]][i];else {ne[p]=tr[ne[t]][i];cnt[p]+=cnt[ne[p]];q[++tt]=p;}}}}int main(){int n,m;
cin>>n>>m;
while(n--){string str;cin>>str;insertt(str);
}
bui();memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=0;i<m;i++){for(int j=0;j<=idx;j++){for(int u=0;u<3;u++){int p=tr[j][u];f[i+1][p]=max(f[i+1][p],f[i][j]+cnt[p]);}}
}int ans=0;
for(int j=0;j<=idx;j++){
ans=max(ans,f[m][j]);
}
cout<<ans;}