hdu4681--String
发布日期:2022-02-02 02:58:06 浏览次数:2 分类:技术文章

本文共 2654 字,大约阅读时间需要 8 分钟。

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的子串

先找出A和B的最长公共子序列,然后再把A和B倒过来,求其最长公共子序列。最后把C的头和尾分别在A和B中标记下来,然后求之。

代码实现:

#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;}


转载地址:https://blog.csdn.net/u010368749/article/details/18620195 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:求最长公共子序列
下一篇:动态规划---hdu--1421 搬寝室

发表评论

最新留言

初次前来,多多关照!
[***.36.149.66]2022年06月19日 00时26分11秒

关于作者

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

最新文章