http://acm.hdu.edu.cn/showproblem.php?pid=4681
枚举A串和B串包含C串的区间 枚举区间端点算左右两端最长公共子序
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 1010
char s1[N],s2[N],s3[N];
int dp1[N][N],dp2[N][N];
struct node
{
int l,r;
}p1[N],p2[N];
int main()
{
int i,j,t,k1,k2,k3,kk=;
scanf("%d",&t);
while(t--)
{
kk++;
memset(dp1,,sizeof(dp1));
memset(dp2,,sizeof(dp2));
scanf("%s%s%s",s1,s2,s3);
k1 = strlen(s1);
k2 = strlen(s2);
k3 = strlen(s3);
for(i = ; i <= k1 ; i++)
for(j = ; j <= k2 ;j++)
{
if(s1[i-]==s2[j-])
dp1[i][j] = dp1[i-][j-]+;
else
dp1[i][j] = max(dp1[i-][j],dp1[i][j-]);
}
for(i = k1 ; i>= ; i--)
for(j = k2 ; j >= ; j--)
{
if(s1[i-]==s2[j-])
dp2[i][j] = dp2[i+][j+]+;
else
dp2[i][j] = max(dp2[i+][j],dp2[i][j+]);
}
int g = ;j=;
for(i = ; i < k1 ; i++)
if(s1[i]==s3[j])
{
j++;int a=i;
if(j<k3)
{
for(a = i+ ; a < k1 ; a++)
{
if(s1[a]==s3[j])
j++;
if(j==k3)
break;
}
}
if(j==k3)
{
g++;
p1[g].l = i;
p1[g].r = a+;
}
j = ;
}
int o=;j=;
for(i = ; i < k2 ; i++)
if(s2[i]==s3[j])
{
j++;int a=i;
if(j<k3)
{
for(a = i+ ; a < k2 ; a++)
{
if(s2[a]==s3[j])
j++;
if(j==k3)
break;
}
}
if(j==k3)
{
o++;
p2[o].l = i;
p2[o].r = a+;
}
j = ;
}
int maxz=;
for(i = ; i <= g ; i++)
for(j = ; j <= o ; j++)
{
int x = dp1[p1[i].l][p2[j].l],x2 = dp2[p1[i].r+][p2[j].r+];
maxz = max(maxz,x+x2);
}
printf("Case #%d: %d\n",kk,maxz+k3);
}
return ;
}