大家好,又见面了,我是你们的朋友全栈君。
很早之前就做过啦
补一下题解
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();
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/127721.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...