hdu4681--String

Problem Description
Given 3 strings A, B, C, find the longest string D which satisfy the following rules:
a) D is the subsequence of A
b) D is the subsequence of B
c) C is the substring of D
Substring here means a consecutive subsequnce.
You need to output the length of D.

Input
The first line of the input contains an integer T(T = 20) which means the number of test cases.
For each test case, the first line only contains string A, the second line only contains string B, and the third only contains string C.
The length of each string will not exceed 1000, and string C should always be the subsequence of string A and string B.
All the letters in each string are in lowercase.

Output
For each test case, output Case #a: b. Here a means the number of case, and b means the length of D.

Sample Input
2aaaaaaaaa aaabcdefacebdfcf

Sample Output
Case #1: 4Case #2: 3

Hint

For test one, D is "aaaa", and for test two, D is "acf".

D是A的子序列，也是B的子序列，C是D的子串

#include

#include

#include

#define M 1007using namespace std;int dp1[M][M],dp2[M][M];char s1[M],s2[M],s3[M],st1[M],st2[M];int z1[M][2],z2[M][2];int len1,len2,len3;int main(){

int t;
cin>>t;
for(int cas=1; cas<=t; cas++)
{
cin>>s1>>s2>>s3;
len1=strlen(s1);
len2=strlen(s2);
len3=strlen(s3);
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
//dp1[][]求的是s1和s2的最大公共子序列
for(int i=1; i<=len1; i++)
for(int j=1; j<=len2; j++)
if(s1[i-1]==s2[j-1])
dp1[i][j]=dp1[i-1][j-1]+1;
else
dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]);
//st1是将s1字符串转过来
for(int i=0; i
st1[i]=s1[len1-i-1];
//st2是将s2字符串转过来
for(int i=0; i
st2[i]=s2[len2-i-1];
//求的是st1和st2的最长公共子序列
for(int i=1; i<=len1; i++)
for(int j=1; j<=len2; j++)
if(st1[i-1]==st2[j-1])
dp2[i][j]=dp2[i-1][j-1]+1;
else
dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1]);
//将s3的起点和终点在s1中的所有情况记录下来
int n1=0,n2=0,k,j;
for(int i=0; i
{
if(s1[i]==s3[0])
{
k=1;
for(j=i+1; j
{
if(s1[j]==s3[k])
k++;
if(k==len3)
break;
}
if(j!=len1)
{
z1[n1][0]=i;
z1[n1++][1]=j;
}
}
}
//将s3的起点和终点在s2中的所有情况记录下来
for(int i=0; i
{
if(s2[i]==s3[0])
{
k=1;
for(j=i+1; j
{
if(s2[j]==s3[k])
k++;
if(k==len3)
break;
}
if(j!=len2)
{
z2[n2][0]=i;
z2[n2++][1]=j;
}
}
}
//枚举所有情况，找出s4最大的长度
int ans=0;
for(int i=0; i
for(int j=0; j
ans=max(ans,dp1[z1[i][0]][z2[j][0]]+dp2[len1-z1[i][1]-1][len2-z2[j][1]-1]);//应为从0开始的所以要减去1
cout<<"Case #"< <<": "< <
}
return 0;}

#### 最新留言

[***.36.149.66]2022年06月19日 00时26分11秒

## 关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！