这个题目是这样的。
给你三个字符串A，B，C，（C一定是A和B的一个公共子序列）。
现在要求你构造出一个串D，使得D同时为A和B的子序列，且C是D的一个连续子串。求D的最大可能长度。
很简单的一个DP题。
其实这个题目有三个预处理就可以搞定了。
1、f1[i][j]：A的前i个字符，B的前J个字符的最长公共子序列。
2、f2[i][j]：A的i个字符以后，B的第J个字符以后的字符的最长公共子序列。
3、A和B串以某个位置开始作为C的子序列时，最近的匹配距离（最近匹配完的那个地方）。
有了这三个预处理，剩下的只要直接暴力枚举A和B中匹配的开始位置即可。
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 1015
using namespace std;
int f1[maxn][maxn],f2[maxn][maxn],pos1[maxn],pos2[maxn],L1,L2,L,ans,cas=0,t;
char s1[maxn],s2[maxn],s[maxn];
int main()
{
scanf("%d",&t);
while (t--)
{
memset(f1,0,sizeof f1);
memset(f2,0,sizeof f2);
memset(s,0,sizeof s);
memset(pos1,0,sizeof pos1);
memset(pos2,0,sizeof pos2);
memset(s1,0,sizeof s1);
memset(s2,0,sizeof s2);
scanf("%s",s1+1);scanf("%s",s2+1);scanf("%s",s+1);
L1=strlen(s1+1),L2=strlen(s2+1),L=strlen(s+1);
for (int i=1; s1[i]; i++)
for (int j=1; s2[j]; j++)
{
f1[i][j]=max(f1[i-1][j],f1[i][j-1]);
if (s1[i]==s2[j])
f1[i][j]=max(f1[i][j],f1[i-1][j-1]+1);
}
f2[L1+1][L2]=f2[L1][L2+1]=f2[L1+1][L2+1]=0;
for (int i=L1; i>0; i--)
for (int j=L2; j>0; j--)
{
f2[i][j]=max(f2[i+1][j],f2[i][j+1]);
if (s1[i]==s2[j])
f2[i][j]=max(f2[i][j],f2[i+1][j+1]+1);
}
for (int i=1; s1[i]; i++)
{
if (s1[i]!=s[1])
{
pos1[i]=0;
continue;
}
int cur=1,j=i;
for (; s1[j]; j++)
{
if (s1[j]==s[cur]) cur++;
if (!s[cur]) break;
}
if (!s[cur]) pos1[i]=j;
else pos1[i]=0;
}
for (int i=1; s2[i]; i++)
{
if (s2[i]!=s[1])
{
pos2[i]=0;
continue;
}
int cur=1,j=i;
for (;s2[j]; j++)
{
if (s2[j]==s[cur]) cur++;
if (!s[cur]) break;
}
if (!s[cur]) pos2[i]=j;
else pos2[i]=0;
}
ans=L;
for (int i=1; s1[i]; i++)
{
if (pos1[i]==0) continue;
for (int j=1; s2[j]; j++)
{
if (pos2[j]==0) continue;
ans=max(ans,L+f1[i-1][j-1]+f2[pos1[i]+1][pos2[j]+1]);
}
}
printf("Case #%d: %d
",++cas,ans);
}
return 0;
}