博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
动态规划 - 最长公共子序列(LCS)
阅读量:5878 次
发布时间:2019-06-19

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

最长公共子序列也是动态规划中的一个经典问题。

有两个字符串 S1 和 S2,求一个最长公共子串,即求字符串 S3,它同时为 S1 和 S2 的子串,且要求它的长度最长,并确定这个长度。这个问题被我们称为最长公共子序列问题。

与求最长递增子序列一样,我们首先将原问题分割成一些子问题,我们用 dp[i][j]表示 S1 中前 i 个字符与 S2 中前 j 个字符分别组成的两个前缀字符串的最长公共子串长度。

显然的,当 i、 j 较小时我们可以直接得出答案,如 dp[0][j]必等于 0。那么,假设我们已经求得 dp[i][j](0<=i<x,0<=j<y)的所有值,考虑如何由这些值继而推得 dp[x][y],求得 S1 前 x 个字符组成的前缀子串和 S2 前 y 个字符 组成的前缀子串的最长公共子序列长度。若 S1[x] = =S2[y],即 S1 中的第 x 个字 符和 S2 中的第 y 个字符相同,同时由于他们都是各自前缀子串的最后一个字符, 那么必存在一个最长公共子串以 S1[x]或 S2[y]结尾,其它部分等价于 S1 中前 x-1 个字符和 S2中前 y-1个字符的最长公共子串。所以这个子串的长度比 dp[x-1][y-1] 又增加 1,即 dp[x][y] = dp[x-1][y-1] + 1。

相反的,若 S1[x] != S2[y],此时其最长 公共子串长度为 S1 中前 x-1 个字符和 S2 中前 y 个字符的最长公共子串长度与 S1 中前 x 个字符和 S2 中前 y-1 个字符的最长公共子串长度的较大者,即在两种 情况下得到的最长公共子串都不会因为其中一个字符串又增加了一个字符长度 发生改变。综上所述, dp[x][y] = max{dp[x-1][y],dp[x][y-1]}。

最长公共子序列的递推条件

假设有两个字符串S1和S2,其中S1的长度为n,S2的长度为m,用dp[i][j]表示S1前i个字符组成的前缀子串与S2前j个字符组成的前缀子串的最长公共子串长度,如下:

dp[0][j] = dp[i][0] = 0,其中j>=0 && j<=m,i>=0 && i<=n;

dp[i][j] = dp[i-1][j-1]+1;(S1[i] = S2[j])

dp[i][j] = max{dp[i-1][j],dp[i][j-1]};(S1[i] != S2[j])

最后可以求得dp[n][m]中保存的值即为两个原始字符串的最长公共子序列长度。

按照上面的公式可以写出最长公共子序列的算法

#include "stdafx.h"#include 
#include
using namespace std;#define MAXSIZE 101char str1[MAXSIZE];char str2[MAXSIZE];//'l'表示dp[i][j] = dp[i][j] = dp[i - 1][j];//‘q’表示dp[i][j] = dp[i][j] = dp[i - 1][j];//'u'表示dp[i][j] = dp[i][j - 1];char path[MAXSIZE][MAXSIZE];int dp[MAXSIZE][MAXSIZE];void printLCS(int i, int j){ if (i == 0 || j == 0) return; if (path[i][j] == 'q') { printLCS(i - 1, j - 1); cout << str1[i-1] << ' '; } else if (path[i][j] == 'u') printLCS(i - 1, j); else printLCS(i, j - 1); } int main(){ int n, m; cin >> str1 >> str2; n = strlen(str1); m = strlen(str2); //初始化 for (int i = 0; i < n;i++) for (int j = 0; j < m; j++) dp[i][j] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; path[i][j] = 'q'; } else { if (dp[i - 1][j] >= dp[i][j - 1]) { dp[i][j] = dp[i - 1][j]; path[i][j] = 'u'; } else { dp[i][j] = dp[i][j - 1]; path[i][j] = 'l'; } } } cout << dp[n][m] << endl; printLCS(n, m); return 0;}
View Code

测试实例:

str1 = “abcbdab”;str2 = "bdcaba"。

输出如下:

虽然str1和str2的最长公共子序列有多个,根据dp[n][m]进行递归输出,只输出一个最长公共子序列。

转载地址:http://njdix.baihongyu.com/

你可能感兴趣的文章
如何对HTML进行编码和解码?
查看>>
SEO基础问题:4.什么是长尾关键词?
查看>>
jqgrid 根据ID去掉多余不能动滚动条
查看>>
作用域
查看>>
继承过程中对函数中this的认识
查看>>
进程通信方式
查看>>
JQ表单选择器和CSS3表单选择器
查看>>
Spark进阶之路-日志服务器的配置
查看>>
about SpringBoot学习后记
查看>>
Hibernate - 多对多中关联对象作查询条件
查看>>
springmvc 日期转换器
查看>>
java String-StringBuffer-StringBuilder
查看>>
python使用matplotlib:subplot绘制多个子图
查看>>
第二次作业
查看>>
汉字unicode码表范围和常用汉字unicode码
查看>>
Web API总结
查看>>
jquery.min.js v1.10.3版本autocomplete方法会在text前添加搜索出多少项的文本信息 要去除...
查看>>
数据结构堆排序
查看>>
Mysql怎么判断繁忙 checkpoint机制 innodb的主要参数
查看>>
MyGeneration学习笔记(11) :dOOdad的架构(Architectures)
查看>>