字符串DP
题意：给你三个字符串a,b,c求字符串d的长度。
字符串d满足的要求：是a和b的公共子序列，c是它的子串。
定义dp1[i][j]表示a的第 i 位与b的第 j 位之前相同的子序列长度（包括 i ，j），dp2[i][j]表示a的第 i 位与b的第 j 位之后相同的子序列长度（包括 i ，j）。
查找c的首尾字符在a 和b 的位置，求出c首字符之前a和b的公共子序列的长度以及c尾字符之后a和b的公共子序列的长度，加上c的长度即为所求。
#include<stdio.h> #include<string.h> #define maxn 1010 #define max(a,b) (a)>(b)?(a):(b) char a[maxn],b[maxn],c[maxn]; int dp1[maxn][maxn],dp2[maxn][maxn]; int n,m,len; int sa[maxn][3],sb[maxn][3]; void LCS() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i]==b[j]) dp1[i][j]=dp1[i-1][j-1]+1; else dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]); } for(int i=n;i>0;i--) for(int j=m;j>0;j--) { if(a[i]==b[j]) dp2[i][j]=dp2[i+1][j+1]+1; else dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1]); } } void Deal() { int k,j,t1,t2; t1=t2=0; for(int i=1;i<=n;i++) if(a[i]==c[1]) { for(j=i+1,k=1;j<=n;j++) { if(a[j]==c[k+1]) k++; if(k==len) break; } if(k==len) sa[t1][0]=i,sa[t1++][1]=j; } for(int i=1;i<=m;i++) if(b[i]==c[1]) { for(j=i+1,k=1;j<=m;j++) { if(b[j]==c[k+1]) k++; if(k==len) break; } if(k==len) sb[t2][0]=i,sb[t2++][1]=j; } int ans=0; for(int i=0;i<t1;i++) for(int j=0;j<t2;j++) ans=max(ans,dp1[sa[i][0]-1][sb[j][0]-1]+dp2[sa[i][1]+1][sb[j][1]+1]); printf("%d ",len+ans); } int main() { int T,cas=1; scanf("%d",&T); while(T--) { scanf("%s%s%s",a+1,b+1,c+1); n=strlen(a+1); m=strlen(b+1); len=strlen(c+1); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); printf("Case #%d: ",cas++); LCS(); Deal(); } return 0; }