开发者社区> 华山青竹> 正文

最长公共子序列(POJ1458)

简介: 题目链接:http://poj.org/problem?id=1458 题目大意:给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序一致。
+关注继续查看

题目链接:http://poj.org/problem?id=1458

题目大意:给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序一致。

输入有若干行,每行是两个字符串。对每一行输入的两个字符串,输出最长公共子串的长度。

Sample Input
abcfbc abfcab
programming contest
abcd mnp

Sample Output
4
2
0

算法分析

参考1:北大郭炜老师mooc课程
参考2:http://blog.csdn.net/u013480600/article/details/40741333

参考3:http://blog.csdn.net/lz161530245/article/details/76943991

输入两个串s1,s2,
设MaxLen(i,j)表示:s1的左边i个字符形成的子串,与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算)
MaxLen(i,j) 就是本题的“状态”
假定 len1 = strlen(s1),len2 = strlen(s2)
那么题目就是要求 MaxLen(len1,len2)

显然:
MaxLen(n,0) = 0 ( n= 0…len1)
MaxLen(0,n) = 0 ( n=0…len2)
递推公式:
if(s1[i-1] == s2[j-1]) //s1的最左边字符是s1[0]
    MaxLen(i,j) = MaxLen(i-1,j-1) + 1;
else
    MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );
时间复杂度O(mn),其中m,n是两个字串长度。

关于证明,可以阅读参考2参考3的证明过程。大概过程记录如下:

我们用Ax表示序列A的连续前x项构成的子序列,即Ax= a1,a2,……ax, By= b1,b2,……by, 我们用LCS(x, y)表示它们的最长公共子序列长度,那原问题等价于求LCS(m,n)。为了方便我们用L(x, y)表示Ax和By的一个最长公共子序列。
让我们来看看如何求LCS(x, y)。我们令x表示子序列,考虑最后一项

第(1)种情况:Ax = By
那么它们L(Ax, By)的最后一项一定是这个元素!
为什么呢?为了方便,我们令t=Ax=By, 我们用反证法:假设L(x,y)最后一项不是t,
则要么L(x,y)为空序列(别忘了这个),要么L(x,y)的最后一项是Aa=Bb ≠ t, 且显然有a<x,b<y。无论是哪种情况我们都可以把t接到这个L(x,y)后面,从而得到一个更长的公共子序列。矛盾!
如果我们从序列Ax中删掉最后一项ax得到Ax-1,从序列By中也删掉最后一项by得到By-1,(多说一句角标为0时,认为子序列是空序列),则我们从L(x,y)也删掉最后一项t得到的序列是L(x – 1, y - 1)。为什么呢?和上面的道理相同,如果得到的序列不是L(x - 1, y - 1),则它一定比L(x - 1, y - 1)短,那么它后面接上元素t得到的子序列L(x,y)也比L(x - 1, y - 1)接上元素t得到的子序列短,这与L(x, y)是最长公共子序列矛盾。
因此L(x,y)=L(x-1,y-1)最后接上元素t,也就是说:
LCS(Ax, By) = LCS(x - 1, y - 1) + 1

第(2)种情况:Ax ≠ By
仍然设t=L(Ax,By)的最后一个字符,或者L(Ax,By)是空序列(这时t是未定义值不等于任何值)。
则t≠Ax和t≠By至少有一个成立,因为t不能同时等于两个不同的值嘛!
(2.1) 如果t≠Ax,则有L(x,y)=L(x-1,y),因为根本没Ax的事嘛。
       也就是说:LCS(x,y) = LCS(x – 1, y)
(2.2) 如果t≠By,同理有L(x,y)= L(x,y-1)。
       也就是说:LCS(x,y) = LCS(x, y – 1)
可是,我们事先并不知道t,由定义,我们取最大的一个,因此这种情况下,有LCS(x,y)=max(LCS(x–1,y),LCS(x,y–1))。


看看目前我们已经得到了什么结论:
LCS(x,y) = 
    (1) LCS(x - 1,y - 1) + 1 如果Ax = By
    (2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
这是一个显然的递推式,光有递推可不行,初值是什么呢?
显然,一个空序列和任何序列的最长公共子序列都是空序列!所以我们有:
LCS(x,y) = 
    (1) LCS(x - 1,y - 1) + 1     如果Ax = By
    (2) max(LCS(x – 1, y) , LCS(x, y – 1))     如果Ax ≠ By
    (3) 0     如果x=0或者y=0

到此我们求出了计算最长公共子序列长度的递推公式。我们实际上计算了一个(n + 1)行(m + 1)列的表格(行是0..n,列是0..m),也就这个二维度数组LCS(n,m)。
证明过程

 

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 char sz1[5005];
 5 char sz2[5005];
 6 int maxLen[5005][5005];
 7 int main()
 8 {
 9     while( cin >> sz1 >> sz2 ) 
10     {
11         int length1 = strlen( sz1);
12         int length2 = strlen( sz2);
13         int nTmp;
14         int i,j;
15         for( i = 0;i <= length1; i ++ ) maxLen[i][0] = 0;
16         for( j = 0;j <= length2; j ++ ) maxLen[0][j] = 0;
17         for( i = 1;i <= length1;i ++ ) 
18         {
19             for( j = 1; j <= length2; j ++ ) 
20             {
21                 if( sz1[i-1] == sz2[j-1] )
22                     maxLen[i][j] = maxLen[i-1][j-1] + 1;
23                 else
24                     maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);
25             }
26         }
27         cout << maxLen[length1][length2] << endl;
28     }
29     return 0;
30 }

上面的题目并没有要求输出最长的公共子序列。假如要输出最长公共子序列,可以阅读参考3的代码:(也可以暂时跳过,本文末尾有代码实现。) 

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 int LCSLength(char* str1, char* str2, int **b)
 5 {
 6     int i,j,length1,length2,len;
 7     length1 = strlen(str1);
 8     length2 = strlen(str2);
 9 
10     //双指针的方法申请动态二维数组
11     int **c = new int*[length1+1]; //共有length1+1行
12     for(i = 0; i < length1+1; i++)
13         c[i] = new int[length2+1];//共有length2+1列
14 
15     for(i = 0; i < length1+1; i++)
16         c[i][0]=0;        //第0列都初始化为0
17     for(j = 0; j < length2+1; j++)
18         c[0][j]=0;        //第0行都初始化为0
19 
20     for(i = 1; i < length1+1; i++)
21     {
22         for(j = 1; j < length2+1; j++)
23         {
24             if(str1[i-1]==str2[j-1])//由于c[][]的0行0列没有使用,c[][]的第i行元素对应str1的第i-1个元素
25             {
26                 c[i][j]=c[i-1][j-1]+1;
27                 b[i][j]=0;          //输出公共子串时的搜索方向
28             }
29             else if(c[i-1][j]>c[i][j-1])
30             {
31                 c[i][j]=c[i-1][j];
32                 b[i][j]=1;
33             }
34             else
35             {
36                 c[i][j]=c[i][j-1];
37                 b[i][j]=-1;
38             }
39         }
40     }
41     /*
42     for(i= 0; i < length1+1; i++)
43     {
44     for(j = 0; j < length2+1; j++)
45     printf("%d ",c[i][j]);
46     printf("\n");
47     }
48     */
49     len=c[length1][length2];
50     for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组
51         delete[] c[i];
52     delete[] c;
53     return len;
54 }
55 void PrintLCS(int **b, char *str1, int i, int j)
56 {
57     if(i==0 || j==0)
58         return ;
59     if(b[i][j]==0)
60     {
61         PrintLCS(b, str1, i-1, j-1);//从后面开始递归,所以要先递归到子串的前面,然后从前往后开始输出子串
62         printf("%c",str1[i-1]);//c[][]的第i行元素对应str1的第i-1个元素
63     }
64     else if(b[i][j]==1)
65         PrintLCS(b, str1, i-1, j);
66     else
67         PrintLCS(b, str1, i, j-1);
68 }
69 
70 int main(void)
71 {
72     char str1[100],str2[100];
73     int i,length1,length2,len;
74     printf("请输入第一个字符串:");
75     gets(str1);
76     printf("请输入第二个字符串:");
77     gets(str2);
78     length1 = strlen(str1);
79     length2 = strlen(str2);
80     //双指针的方法申请动态二维数组
81     int **b = new int*[length1+1];
82     for(i= 0; i < length1+1; i++)
83         b[i] = new int[length2+1];
84     len=LCSLength(str1,str2,b);
85     printf("最长公共子序列的长度为:%d\n",len);
86     printf("最长公共子序列为:");
87     PrintLCS(b,str1,length1,length2);
88     printf("\n");
89     for(i = 0; i < length1+1; i++)//释放动态申请的二维数组
90         delete[] b[i];
91     delete[] b;
92     system("pause");
93     return 0;
94 }
求最长公共子序列长度并输出最长公共子序列

 查找并输出最长公共子序列也可以参考https://wenku.baidu.com/view/7e96c94f2b160b4e767fcfc9.html

 

空间上的优化:

观察上面算法中的关键代码:

for( i = 1;i <= length1;i ++ ) 
{
    for( j = 1; j <= length2; j ++ ) 
    {
        if( sz1[i-1] == sz2[j-1] ) maxLen[i][j] = maxLen[i-1][j-1] + 1;
        else  maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);
    }
}

可以发现,计算maxLen数组第i行时用到的只有第i行与第i-1行。我们的目的是要计算maxLen[length1][length2],所以,可以考虑只保存两行即可,也就是使用滚动数组只保存两行。

 代码如下:(参考来源

cur表示当前需要求的那一行的下标。

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 char sz1[5005];
 5 char sz2[5005];
 6 int maxLen[2][5005];
 7 int main()
 8 {
 9     int i,j,length1,length2,cur=0;
10     
11     while( cin >> sz1 >> sz2 ) 
12     {
13         length1 = strlen( sz1);
14         length2 = strlen( sz2);
15         for( i=0;i<2; i++ ) maxLen[i][0]=0;
16         for( j=0;j<=length2;j++ ) maxLen[0][j]=0;
17         cur=0;
18         
19         for( i = 1;i <= length1;i ++ ) 
20         {
21             cur ^= 1;
22             for( j = 1; j <= length2; j ++ ) 
23             {
24                 if( sz1[i-1] == sz2[j-1] )
25                     maxLen[cur][j] = maxLen[cur^1][j-1] + 1;
26                 else
27                     maxLen[cur][j] = max(maxLen[cur][j-1],maxLen[cur^1][j]);
28             }
29         }
30         cout << maxLen[cur][length2] << endl;
31     }
32     return 0;
33 }
View Code

 

下面修改一下代码寻找出一个最长公共子序列。 

上面经过空间优化后,也只是寻找到了最长公共子序列的长度,那么如何得到一个最长公共子序列而仅仅不是简单的长度呢?其实我们离真正的答案只有一步之遥!

 

 

 参考上图,我们建立一个二维数组ans[][],在寻找最长公共子序列的长度时用ans[i][j]记录LCS(i,j)是如何来的(从左边、上边或是从左上),ans[i][j]等于1,2,3分别表示:

L(x,y) = L(x, y – 1) 

L(x,y)= L(x – 1, y)

L(x,y) = L(x,- 1 y- 1)末尾接上Ax 

当ans[i][j]等于3时字符串1的第i个字符(或字符串2的第j个字符,其实两者相同)肯定是最长公共子序列的一部分,要保留到temp[ ]中。所以从ans[][]右下角逆推即可求出temp[ ],然后逆序输出temp[]即可。代码如下:

 1 //51Nod动态规划教程例题 求最长公共子序列的长度并输出一个最长公共子序列
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 #define maxN 5005
 6 char sz1[maxN];
 7 char sz2[maxN];
 8 int maxLen[2][maxN];
 9 char ans[maxN][maxN]={0};
10 
11 void printLCS(int len1,int len2);//输出一个最长公共子序列 
12 int main()
13 {
14     int i,j,length1,length2,cur=0;
15     freopen("poj1458.in","r",stdin);
16     while( cin >> sz1 >> sz2 ) 
17     {
18         memset(ans,0,sizeof(char)*maxN*maxN);
19         length1 = strlen( sz1);
20         length2 = strlen( sz2);
21         for( i=0;i<2; i++ ) maxLen[i][0]=0;
22         for( j=0;j<=length2;j++ ) maxLen[0][j]=0;
23         cur=0;
24         
25         for( i = 1;i <= length1;i ++ ) 
26         {
27             cur ^= 1;
28             for( j = 1; j <= length2; j ++ ) 
29             {
30                 if( sz1[i-1] == sz2[j-1] )
31                 {
32                     maxLen[cur][j] = maxLen[cur^1][j-1] + 1;
33                     ans[i][j]=3;
34                 }
35                 else
36                 {
37                     //maxLen[cur][j] = max(maxLen[cur][j-1],maxLen[cur^1][j]);
38                     if(maxLen[cur][j-1]>maxLen[cur^1][j])
39                     {
40                         maxLen[cur][j]=maxLen[cur][j-1];
41                         ans[i][j]=1;
42                     }
43                     else
44                     {
45                         maxLen[cur][j]=maxLen[cur^1][j];
46                         ans[i][j]=2;
47                     }
48                 }
49             }
50         }
51         cout << maxLen[cur][length2] << endl;
52         if(maxLen[cur][length2]>0) printLCS(length1,length2);
53     }
54     return 0;
55 }
56 void printLCS(int len1,int len2)//输出一个最长公共子序列
57 {
58     char temp[maxN];
59     int i=len1,j=len2,k=0;
60     while(ans[i][j]!=0)
61     {
62         if(ans[i][j]==3) { temp[k++]=sz1[i-1]; i--;j--; }
63         else if(ans[i][j]==1)
64         {
65             j--;
66         }
67         else if(ans[i][j]==2)
68         {
69             i--;
70         }
71     }
72     for(k--;k>=0;k--) printf("%c",temp[k]);
73     printf("\n");
74 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
14233 0
最长公共子序列(POJ1458)
题目链接:http://poj.org/problem?id=1458 题目大意:给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序一致。
859 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23541 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20283 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
11984 0
poj 1631 Bridging signals【最长上升子序列】
点击打开链接 Bridging signals Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 10951   Accepted: 6000 Descriptio...
671 0
使用NAT网关轻松为单台云服务器设置多个公网IP
在应用中,有时会遇到用户询问如何使单台云服务器具备多个公网IP的问题。 具体如何操作呢,有了NAT网关这个也不是难题。
37304 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36371 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载