题意：略。
思路：找到a、b中所有的包含c序列的起点和终点位置，然后从中找出起点前和终点后的公共子序列的长度和c序列长度的和的最大值。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t;
char a[1005],b[1005],c[1005];
int la,lb,lc;
int as[1005],ae[1005],bs[1005],be[1005],anum,bnum;
int f[1005][1005],ff[1005][1005];
void lcs(int s1,int e1,int s2,int e2)
{
memset(f,0,sizeof(f));
for(int i=s1;i<e1;i++)
{
for(int j=s2;j<e2;j++)
{
if(a[i]==b[j])
{
f[i+1][j+1]=f[i][j]+1;
}
else f[i+1][j+1]=max(f[i+1][j],f[i][j+1]);
}
}
memset(ff,0,sizeof(ff));
for(int i=e1-1;i>=s1;i--)
{
for(int j=e2-1;j>=s2;j--)
{
if(a[i]==b[j])
{
ff[i][j]=ff[i+1][j+1]+1;
}
else
{
ff[i][j]=max(ff[i+1][j],ff[i][j+1]);
}
}
}
//cout<<s1<<" "<<e1<<" "<<s2<<" "<<e2<<" "<<f[e1-1][e2-1]<<endl;
//return f[e1][e2];
}
int main()
{
int ca=0;
scanf("%d",&t);
while(t--)
{
anum=bnum=0;
scanf("%s%s%s",a,b,c);
la=strlen(a);
lb=strlen(b);
lc=strlen(c);
for(int i=0;i<la;i++)
{
if(a[i]==c[0])
{
int num=1;
for(int j=i+1;j<la;j++)
{
if(a[j]==c[num])
{
num++;
if(num==lc)
{
as[anum]=i;
ae[anum]=j;
anum++;
break;
}
}
}
}
}
for(int i=0;i<lb;i++)
{
if(b[i]==c[0])
{
int num=1;
for(int j=i+1;j<lb;j++)
{
if(b[j]==c[num])
{
num++;
if(num==lc)
{
bs[bnum]=i;
be[bnum]=j;
bnum++;
break;
}
}
}
}
}
int ans=0;
lcs(0,la,0,lb);
for(int i=0;i<anum;i++)
{
for(int j=0;j<bnum;j++)
{
int ss=f[as[i]][bs[j]]+ff[ae[i]+1][be[j]+1]+lc;
if(ss>ans)ans=ss;
}
}
printf("Case #%d: %d\n",++ca,ans);
}
return 0;
}