学步园

题意：给定字符串A，B，C，寻找一个最长的D，满足以下条件:

1）D是A的子序列

2）D是B的子序列

3) C是D的子串 （子串是指连续的子字符串）

求出D的长度

思路：先对A,B正向求最长公共子序列记录在f(i,j)中，再对A、B逆向求最长公共子序列记录在g(i,j)中。

在A和B中寻找子序列C，对于C在A、B中的每个起点，只需要找出C在其中结束最近的位置就可以了。例如A是abbb中，C是ab，那么只需要找到起始位置1和终止位置2就可以了，记为(1,2)。然后，假设在A中找到了(a,b)，在B中找到了(c,d)，那么，如果C占用的是A中的(a,b)，还有B中的(c,d)，那么这时候D的值就是lenC+f(a-1,b-1)+g(a+1,b+1)。所以只要枚举C占用的位置，每次算出相应的lenC+f(a-1,b-1)+g(a+1,b+1)最后取最大值即可。

对于C在A、B中占用位置的计算，我们可以这样做：用一个p1指向C中的头，p2指向A中的第一个和C[1]相等的位置，如果p1指向的元素和p2指向的元素相等，那么p1和p2都向后移一位，否则p2继续在A中向后寻找与p1指向元素相等的元素。在B中的时候也一样。

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 1005
using namespace std;

int T;
int f[MAXN][MAXN],g[MAXN][MAXN];
char A[MAXN],B[MAXN],C[MAXN];

void findpos(char tar[],int beg[],int end[],int &cnt)//在tar[]中寻找C，头尾分别记录在beg[]和end[]中
{
	int lentar=strlen(tar+1),p1,p2;
	cnt=0;
	int lenc=strlen(C+1);
	for(int i=1;i+lenc-1<=lentar;++i)
	{
		if(tar[i]==C[1])
			{
				p1=1,p2=i;
				while(p1<=lenc && p2<=lentar)
				{
					while(p2<=lentar && tar[p2]!=C[p1]) ++p2;//否则p2继续在A中向后寻找与p1指向元素相等的元素
					if(p2<=lentar && tar[p2]==C[p1]) ++p1,++p2;//如果p1指向的元素和p2指向的元素相等，那么p1和p2都向后移一位
				}
				if(p1>lenc) beg[cnt]=i,end[cnt]=p2-1,cnt++;
			}
	}
}

int solve()
{
	int lena=strlen(A+1),lenb=strlen(B+1),lenc=strlen(C+1);
	
	for(int i=0;i<=lena;++i)                         //正向计算最长公共子序列
		for(int j=0;j<=lenb;++j)
		if(!i || !j) f[i][j]=0;
		else if(A[i]==B[j]) f[i][j]=f[i-1][j-1]+1;
		else f[i][j]=max(f[i-1][j],f[i][j-1]);
	
	
	for(int i=lena+1;i>0;--i)                       //逆向计算最长公共子序列
		for(int j=lenb+1;j>0;--j)
		if(i==lena+1 || j==lenb+1) g[i][j]=0;
		else if(A[i]==B[j]) g[i][j]=g[i+1][j+1]+1;
		else g[i][j]=max(g[i+1][j],g[i][j+1]);
	
	int begA[MAXN],endA[MAXN],cntA;
	findpos(A,begA,endA,cntA);
	
	int begB[MAXN],endB[MAXN],cntB;
	findpos(B,begB,endB,cntB);
	
	int ans=0;
	for(int i=0;i<cntA;++i)
	for(int j=0;j<cntB;++j) ans=max(ans,lenc+f[begA[i]-1][begB[j]-1]+g[endA[i]+1][endB[j]+1]);
	return ans;
}
int main()
{
	scanf("%d",&T); getchar();
	int ca=1;
	while(T--)
	{
		gets(A+1); gets(B+1); gets(C+1);
		printf("Case #%d: %d\n",ca++,solve());
	}
}