做ptt网站/什么搜索引擎搜索最全

题目

给定三个大写字母串，串长都在1到100之间，分别记为s1,s2,virus

求s1和s2的最长公共子序列，且该子序列中不包含病毒串virus，

要求最后输出大写字母串，而非长度，不存在输出0

题解

dp[i][j][k]表示只考虑s1的前i个字母和s2的前j个字母的最长公共子序列，且该子序列匹配到了病毒串的第k位

想象dp[i][j][k]构造的序列已经存在，每次两种选择，

①i与j相同，把这一位加到子序列末尾，则子序列当前和病毒串的最长匹配位置，由kmp连跳next数组求得now

②i与j不同，无法补至末尾，用dp[i][j-1][k]和dp[i-1][j][k]来更新dp[i][j][k]

kmp是保留最优子结构的很自然的做法，也注意到，kmp的匹配串只需保留最后一个字母即可

本题特殊之处，在于加了一维之后，没有dp[i-1][j-1]+1>=max(dp[i][j-1],dp[i-1][j])的性质，

所以，必须用dp[i][j-1][k]和dp[i-1][j][k]来更新dp[i][j][k]

输出方案时，就用三维的pre[x][y][z]暴力回跳即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int dp[N][N][N],nex[N],ans;
char s[N],t[N],w[N],res[2*N];
int n,m,p,x,y,z,nx,ny,nz;
struct node
{int x,y,z;
}pre[N][N][N],now;
void kmppre(char u[],int len)
{int i=0,j=nex[0]=-1;while(i<len){while(j!=-1&&u[i]!=u[j])j=nex[j];nex[++i]=++j;}
}
bool upd(int &x,int y)
{if(x<y){x=y;return 1;} return 0;
}
int main()
{scanf("%s%s%s",s+1,t+1,w);n=strlen(s+1),m=strlen(t+1),p=strlen(w);kmppre(w,p);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){for(int k=0;k<p;++k){if(upd(dp[i][j][k],dp[i-1][j][k]))pre[i][j][k]=node{i-1,j,k};if(upd(dp[i][j][k],dp[i][j-1][k])) pre[i][j][k]=node{i,j-1,k};if(s[i]==t[j]){int now=k;while(now!=-1&&s[i]!=w[now])now=nex[now];if(upd(dp[i][j][now+1],dp[i-1][j-1][k]+1))pre[i][j][now+1]=node{i-1,j-1,k};}}}}for(int k=0;k<p;++k){if(upd(ans,dp[n][m][k]))now=node{n,m,k};}if(!ans)printf("%d\n",ans);else{res[ans--]='\0';x=now.x,y=now.y,z=now.z;for(;x>=1&&y>=1;){nx=pre[x][y][z].x;ny=pre[x][y][z].y;nz=pre[x][y][z].z;if(nx<x&&ny<y)res[ans--]=s[x];x=nx,y=ny,z=nz;}printf("%s\n",res);}return 0;
}