/*
题意： 有三个字符串A, B, C。 求串D。
D是A, B的公共子序列。
C是D的子串。
求最长的D串.输出长度.
先求出a，b的最长公共子序列，从开头和末尾开始的都要
其中dp1[i][j]表示a中第i个字符之前，b中第j个字符之前的最长公共子序列长
dp2[i][j]表示a中第i个字符之后，b中第j个字符之后的最长公共子序列长
用find找到a中所有c首尾所在位置，在首位置固定的情况下找到末位置最小的即可，因为更长的会使结果值较小，存在结构体重
同理找到b的
num1[i].x,num1[i].y,num2[j].x,num2[j].y
那么d最长为MAX=max(MAX,dp1[num1[i].x][num2[j].x]+dp2[num1[i].y][num2[j].y]+lenc),
就是说包含c的部分已经固定，只要加上之前和之后的最长公共子序列长就好了
*/
# include <stdio.h>
# include <algorithm>
# include <iostream>
# include <string.h>
using namespace std;
int dp1[1010][1010],dp2[1010][1010];
struct node
{
int x;
int y;
};
struct node num1[1010],num2[1010];
int main()
{
int t,i,j,lena,lenb,lenc,k;
char a[1010],b[1010],c[1010];
int cas=0;
while(~scanf("%d",&t))
{
cas=0;
while(t--)
{
scanf("%s%s%s",a,b,c);
lena=strlen(a);
lenb=strlen(b);
lenc=strlen(c);
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
for(i=1; i<=lena; i++) ///dp1
{
for(j=1; j<=lenb; j++)
{
if(a[i-1]==b[j-1])
dp1[i][j]=dp1[i-1][j-1]+1;
else
dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]);
}
}
for(i=lena-1; i>=0; i--) ///dp2
{
for(j=lenb-1; j>=0; j--)
{
if(a[i]==b[j])
dp2[i+1][j+1]=dp2[i+2][j+2]+1;
else
dp2[i+1][j+1]=max(dp2[i+2][j+1],dp2[i+1][j+2]);
}
}
int ans1=0;
for(i=0; i<lena; i++)//枚举c在a中的首尾
{
if(c[0]==a[i])///首位置
{
for(k=1,j=i+1; j<lena; j++)
{
if(a[j]==c[k])
k++;
if(k==lenc)
break;
}
if(k==lenc)
{
num1[ans1].x=i;
num1[ans1].y=j+2;
ans1++;
}
}
}
int ans2=0;
for(i=0; i<lenb; i++)//枚举c在b中的首尾
{
if(c[0]==b[i])///首位置
{
for(k=1,j=i+1; j<lenb; j++)
{
if(b[j]==c[k])
k++;
if(k==lenc)
break;
}
if(k==lenc)
{
num2[ans2].x=i;
num2[ans2].y=j+2;
ans2++;
}
}
}
int MAX=-1;
printf("Case #%d: ",++cas);
for(i=0; i<ans1; i++)
{
for(j=0; j<ans2; j++)
{
MAX=max(MAX,lenc+dp1[num1[i].x][num2[j].x]+dp2[num1[i].y][num2[j].y]);
}
}
printf("%d\n",MAX);
}
}
return 0;
}
原文：http://blog.csdn.net/lp_opai/article/details/43450943