动态规划-最长公共子序列
问题描述
最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列S,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子序列。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子序列,并打印出最长公共子序列。
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串。
最长公共子序列应用
最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。简而言之,百度知道、百度百科都用得上。如判断S1和S2相似的办法是找出他们的公共子序列S3,S3以相同的顺序在S1和S2中出现,但是不必要连续。S3越长,S1和S3就越相似。
用动态规划解决
1 描述一个最长公共子序列(描述最优解的结构)
先介绍LCS问题的性质:记Xm={x0, x1,…xm}和Yn={y0,y1,…,yn}为两个字符串,而Zk={z0,z1,…zk}是它们的LCS,则:
1) 如果xm=yn,那么zk=xm=yn,并且Zk-1是Xm-1和Yn-1的一个LCS;
2)如果xm≠yn,那么当zk≠xm时Z是Xm-1和Y的一个LCS;
3)如果xm≠yn,那么当zk≠yn时Z是Yn-1和X的一个LCS;
2 递归定义最优解的值
有了上面的性质,我们可以得出如下的思路:求两字符串Xm={x0, x1,…xm}和Yn={y0,y1,…,yn}的LCS,如果xm=yn,那么只需求得Xm-1和Yn-1的LCS,并在其后添加xm(yn)即可;如果xm-1≠yn-1,我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS,并且这两个LCS中较长的一个为X和Y的LCS。
记字符串Xi和Yj的一个LCS的长度为c[i,j]。如果i=0或j=0,其中一个的长度为0,因此LCS的长度为0。由LCS问题的最优子结构可得递归式:
/ 0 if i<0 or j<0
c[i,j]= c[i-1,j-1]+1 if i,j>=0 and xi=xj
\ max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj
3 计算LCS的长度(按自底向上的方式计算最优解的值)
上面的公式用递归函数不难求得。但直接递归(自顶向下)会有很多重复计算,我们用从底向上循环求解的思路效率更高。
为了能够采用循环求解的思路,我们用一个矩阵c[0..m,0..n]保存下来当前已经计算好了的c[i,j],当后面的计算需要这些数据时就可以直接从矩阵读取。另外,求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到,相当于在矩阵c[0...m,0...n]中是从c[i-1,j-1],c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j],因此在矩阵中有三种不同的移动方向:向左、向上和向左上方,其中只有向左上方移动时才表明找到LCS中的一个字符(因为c[i-1,j-1]+1 ,if i,j>=0 and xi=xj)。于是我们需要用另外一个矩阵b[1..m,1..n]保存移动的方向。
下面是计算字符串Xm={x0, x1,…xm}和Yn={y0,y1,…,yn}的LCS的长度伪代码:
LCS-LENGTH(X,Y)
m <- length[X]
n <- length[Y]
//i=0 或 j=0
for i <- 0 to m
do c[i,0]= 0
for j <- 0 to n
do c[0,j]= 0
for i=1 to m
do for j=1 to n
do if xi=yj //c[i,j]=c[i-1,j-1]+1 ,if i,j>=0 and xi=xj
then c[i,j]=c[i-1,j-1]+1
b[i,j]="左上方箭头"
else if c[i,j-1]>=c[i-1,j] //max(c[i,j-1],c[i-1,j] ,if i,j>=0 and xi≠xj
then c[i,j]=c[i,j-1]
b[i,j]="左方箭头"
else c[i,j]=c[i-1,j]
b[i,j]="上方箭头"
return c and b
算法时间复杂度O(mn)
具体例子图见《算法导论》P2114 由计算出的结果构造一个最优解
Print-LCS(b,X,i,j)
if i=0 或 j=0
then return
if b[i,j]="左上方箭头"
then Print-LCS(b,X,i-1,j-1)
else if b[i,j]="上方箭头"
then Print-LCS(b,X,i-1,j)
else Print-LCS(b,X,i,j-1)
该运算时间为O(m+n)
相关文章
- 软测路这样规划,3年拿到别人10年的工作成就
- 【BZOJ1489】[HNOI2009]双递增序列(动态规划)
- 【UOJ#275】组合数问题(卢卡斯定理,动态规划)
- 【BZOJ4006】管道连接(动态规划,斯坦纳树)
- 【BZOJ1226】学校食堂(动态规划,状态压缩)
- 【BZOJ3611】大工程(虚树,动态规划)
- 【BZOJ3992】序列统计(动态规划,NTT)
- 【Wannafly挑战赛4】F 线路规划 倍增+Kruskal+归并
- 让你轻松搞懂0-1背包问题(动态规划 C语言版)
- 新建swap分区的规划、挂载和自动挂载示例
- 179、【动态规划】leetcode ——115. 不同的子序列(C++版本)
- 176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)
- 174、【动态规划/贪心算法/滑动窗口】leetcode ——674. 最长连续递增序列:一题多解 (C++版本)
- 170、【动态规划】leetcode ——188. 买卖股票的最佳时机 IV:二维数组+一维数组 (C++版本)
- 动态规划-子序列问题(判断子序列、不同的子序列、两个字符串的删除操作、编辑距离、回文子串、最长回文子序列)
- 西北区域新能源发展规划及运行监管报告:弃光弃风依然严重
- 信息通信十三五规划:支持窄带物联网全国性网络