大家好，又见面了，我是你们的朋友全栈君。
![[USACO12JAN]视频游戏的连击Video Game Combos「建议收藏」](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
![[USACO12JAN]视频游戏的连击Video Game Combos「建议收藏」](https://img-blog.csdn.net/20180909222334623)
很早之前就做过啦
补一下题解
F(i,j)前i个的字符为j的匹配
注意end要累加
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+100;
int n,m;
struct AC_AUTO{
struct Node{
int vis[26];
int fail;
int end;
}AC[N];
int cnt;
inline void Clear(int p){
memset(AC[p].vis,0,sizeof(AC[p].vis));
AC[p].end=0;
AC[p].fail=0;
}
inline void Build(string S){
int R=S.length();
int now=0;
for(int i=0;i<R;i++){
if(!AC[now].vis[S[i]-'A']){
cnt++;
Clear(cnt);
AC[now].vis[S[i]-'A']=cnt;
}
now=AC[now].vis[S[i]-'A'];
}
AC[now].end++;
}
inline void Get_Fail(){
queue<int> Q;
for(int i=0;i<3;i++){
if(AC[0].vis[i]){
AC[AC[0].vis[i]].fail=0;
Q.push(AC[0].vis[i]);
}
}
while(!Q.empty()){
int x=Q.front();
// cout<<x<<" ";
Q.pop();
for(int i=0;i<3;i++){
if(AC[x].vis[i]){
AC[AC[x].vis[i]].fail=AC[AC[x].fail].vis[i];
Q.push(AC[x].vis[i]);
}
else AC[x].vis[i]=AC[AC[x].fail].vis[i];
}
AC[x].end+=AC[AC[x].fail].end;
// cout<<AC[x].end<<'\n';
}
}
int f[1001][1001];
inline void DP(){
int ans=0;
memset(f,-1,sizeof(f));
f[0][0]=0;
for(int i=1;i<=m;i++){
for(int j=0;j<=cnt;j++){
if(f[i-1][j]==-1)continue;
for(int k=0;k<3;k++){
f[i][AC[j].vis[k]]=max(f[i][AC[j].vis[k]],f[i-1][j]+AC[AC[j].vis[k]].end);
}
}
}
for(int i=0;i<=cnt;i++){
ans=max(ans,f[m][i]);
}
cout<<ans;
}
}ACM;
int main(){
// freopen("3119.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++){
string s;
cin>>s;
ACM.Build(s);
}
ACM.Get_Fail();
ACM.DP();
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/127721.html原文链接：https://javaforall.net
