<< 动态规划求最长公共子序列的长度
上篇讲到使用动态规划可以在
θ(mn)
的时间里求出 LCS 的长度，本文将讨论如何输出最长公共子序列。
问题描述：
给定两个序列，例如 X = “ABCBDAB”、Y = “BDCABA”，求它们的最长公共子序列的长度。
下面是求解时的动态规划表，可以看出 X 和 Y 的最长公共子序列的长度为4：
输出一个最长公共子序列并不难（网上很多相关代码），难点在于输出所有的最长公共子序列，因为 LCS 通常不唯一。总之，我们需要在动态规划表上进行回溯 —— 从
table[m][n]
，即右下角的格子，开始进行判断：
-
如果格子
table[i][j]
对应的
X[i-1] == Y[j-1]
，则把这个字符放入 LCS 中，并跳入
table[i-1][j-1]
中继续进行判断；
-
如果格子
table[i][j]
对应的
X[i-1] ≠ Y[j-1]
，则比较
table[i-1][j]
和
table[i][j-1]
的值，跳入值较大的格子继续进行判断；
-
直到 i 或 j 小于等于零为止，倒序输出 LCS 。
如果出现
table[i-1][j]
等于
table[i][j-1]
的情况，说明最长公共子序列有多个，故两边都要进行回溯（这里用到递归）。
从上图的红色路径显示，X 和 Y 的最长公共子序列有 3 个，分别为 “BDAB”、“BCAB”、“BCBA”。
C++代码如下：
// 动态规划求解并输出所有LCS
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
string X = "ABCBDAB";
string Y = "BDCABA";
vector<vector<int>> table; // 动态规划表
set<string> setOfLCS; // set保存所有的LCS
int max(int a, int b)
return (a>b)? a:b;
* 字符串逆序
string Reverse(string str)
int low = 0;
int high = str.length() - 1;
while (low < high)
char temp = str[low];
str[low] = str[high];
str[high] = temp;
++low;
--high;
return str;
* 构造表，并返回X和Y的LCS的长度
int lcs(int m, int n)
// 表的大小为(m+1)*(n+1)
table = vector<vector<int>>(m+1,vector<int>(n+1));
for(int i=0; i<m+1; ++i)
for(int j=0; j<n+1; ++j)
// 第一行和第一列置0
if (i == 0 || j == 0)
table[i][j] = 0;
else if(X[i-1] == Y[j-1])
table[i][j] = table[i-1][j-1] + 1;
table[i][j] = max(table[i-1][j], table[i][j-1]);
return table[m][n];
* 求出所有的最长公共子序列，并放入set中
void traceBack(int i, int j, string lcs_str)
while (i>0 && j>0)
if (X[i-1] == Y[j-1])
lcs_str.push_back(X[i-1]);
if (table[i-1][j] > table[i][j-1])
else if (table[i-1][j] < table[i][j-1])
else // 相等的情况
traceBack(i-1, j, lcs_str);
traceBack(i, j-1, lcs_str);
return;
setOfLCS.insert(Reverse(lcs_str));
int main()
int m = X.length();
int n = Y.length();
int length = lcs(m, n);
cout << "The length of LCS is " << length << endl;
string str;
traceBack(m, n, str);
set<string>::iterator beg = setOfLCS.begin();
for( ; beg!=setOfLCS.end(); ++beg)
cout << *beg << endl;
getchar();
return 0;
}
运行结果：
Java版本的代码：
import java.util.TreeSet;
public class LongestCommonSubsequence {
private String X;
private String Y;
private int[][] table; // 动态规划表
private TreeSet<String> set = new TreeSet<String>();
* 功能：带参数的构造器
public LongestCommonSubsequence(String X, String Y) {
this.X = X;
this.Y = Y;
* 功能：求两个数中的较大者
private int max(int a, int b) {
return (a>b) ? a:b;
* 功能：构造表，并返回X和Y的LCS的长度
private int lcs(int m, int n) {
table = new int[m+1][n+1]; // 表的大小为(m+1)*(n+1)
for(int i=0; i<m+1; ++i) {
for(int j=0; j<n+1; ++j) {
// 第一行和第一列置0
if (i == 0 || j == 0)
table[i][j] = 0;
else if(X.charAt(i-1) == Y.charAt(j-1))
table[i][j] = table[i-1][j-1] + 1;
table[i][j] = max(table[i-1][j], table[i][j-1]);
return table[m][n];
* 功能：回溯，求出所有的最长公共子序列，并放入set中
private void traceBack(int i, int j, String lcs_str) {
while (i>0 && j>0) {
if (X.charAt(i-1) == Y.charAt(j-1)) {
lcs_str += X.charAt(i-1);
else {
if (table[i-1][j] > table[i][j-1])
else if (table[i-1][j] < table[i][j-1])
else { // 相等的情况
traceBack(i-1, j, lcs_str);
traceBack(i, j-1, lcs_str);
return;
set.add(reverse(lcs_str));
* 功能：字符串逆序
private String reverse(String str) {
StringBuffer strBuf = new StringBuffer(str).reverse();
return strBuf.toString();
* 功能：外部接口 —— 打印输出
public void printLCS() {
int m = X.length();
int n = Y.length();
int length = lcs(m,n);
String str = "";
traceBack(m,n,str);
System.out.println("The length of LCS is: " + length);
for(String s : set) {
System.out.println(s);
* 功能：main方法 —— 程序的入口
public static void main(String[] args) {
LongestCommonSubsequence lcs = new LongestCommonSubsequence("ABCBDAB","BDCABA");
lcs.printLCS();
上篇讲到使用动态规划可以在 θ(mn) 的时间里求出 LCS 的长度，本文将讨论如何输出最长公共子序列。问题描述：给定两个序列，例如 X = “ABCBDAB”、Y = “BDCABA”，求它们的最长公共子序列的长度。下面是求解时的动态规划表，可以看出 X 和 Y 的最长公共子序列的长度为4：输出一个最长公共子序列其实并不难，我们只需要在动态规划表的基础上进行回溯 —— 从tabl
问题描述：给定两个序列，例如 X = “ABCBDAB”、Y = “BDCABA”，求它们的
最长公共子序列的长度。
下面是求解时的
动态规划表，可以看出 X 和 Y 的
最长公共子序列的长度为4：
输出一个
最长公共子序列并不难（网上很多相关代码），难点在于
输出所有的
最长公共子序列，因为 LCS 通常不唯一。
我们需要在
动态规划表上进行回溯 —— 从c[m][n]，即右下角的格子，开始进行判断：
给定序列X={ X1，X2，....Xn }、Y={ Y1，Y2，...Ym }找出它们的最大子序列Z={ Z1，Z2，...Zk }比如：X={ A,B ,C,B,D,A,B }、Y={ B,D,C,A,B,A }，它们的最大子序列
Z={ B,C,B,A}。
c[i][j]表示长度为i的X和长度为j的Y的最长子序列，c[0][j]=0，c[i][0]=0，任一序列与空序列的最长
CSDN-Ada助手:
AES加密算法的C++实现
努力摸鱼划水不掉队:
拓扑排序（Topological Sorting）
破达达里奥.:
Linux网络编程：socket文件传输范例
33870:
算术表达式的合法性判断与求值（下）
序章·谲:
