题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4681
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = ;
const int INF = 0x3f3f3f; char a[maxn],b[maxn],c[maxn];
int dp1[maxn][maxn];
int dp2[maxn][maxn]; void Lcs1(char* s1,char* s2,int m,int n){
for(int i=;i<=m;i++)
for(int j=;j<=n;j++){
if(s1[i-] == s2[j-]) dp1[i][j] = dp1[i-][j-] + ;
else if(dp1[i-][j]>dp1[i][j-]) dp1[i][j] = dp1[i-][j];
else dp1[i][j] = dp1[i][j-];
}
}
void Lcs2(char* s1,char* s2,int m,int n){
for(int i=m-;i>=;i--)
for(int j=n-;j>=;j--){
if(s1[i+] == s2[j+]) dp2[i][j] = dp2[i+][j+] + ;
else if(dp2[i+][j]>dp2[i][j+]) dp2[i][j] = dp2[i+][j];
else dp2[i][j] = dp2[i][j+];
}
} int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
int T;
scanf("%d",&T);
for(int t=;t<=T;t++){
memset(dp1,,sizeof(dp1));
memset(dp2,,sizeof(dp2)); scanf("%s%s%s",a,b,c); int lena = strlen(a), lenb = strlen(b), lenc = strlen(c);
Lcs1(a,b,lena,lenb); Lcs2(a,b,lena,lenb); int ans = lenc;
int left1[maxn],right1[maxn];
int lcnt1=,rcnt1=;
int left2[maxn],right2[maxn];
int lcnt2=,rcnt2=;
for(int i=;i<lena;i++){
if(a[i] == c[]){
int cnt = ;
for(int j=i+;j<lena;j++){
if(a[j] == c[cnt]) cnt++;
if(cnt == lenc){
left1[lcnt1++] = i;
right1[rcnt1++] = j;
break;
}
}
} }
for(int i=;i<lenb;i++){
if(b[i] == c[]){
int cnt = ;
for(int j=i+;j<lenb;j++){
if(b[j] == c[cnt]) cnt++;
if(cnt == lenc){
left2[lcnt2++] = i;
right2[rcnt2++] = j;
break;
}
}
}
}
for(int i=;i<lcnt1;i++)
for(int j=;j<lcnt2;j++){
ans = max(ans,dp1[left1[i]][left2[j]] + lenc + dp2[right1[i]][right2[j]] );
}
printf("Case #%d: %d\n",t,ans); }
}