今天实现的算法是求解最长公共子序列,在字母表Σ上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度并输出该最长公共子序列。这里,A=a1a2...an的子序列是一个形式为ai1ai2...aik的字符串,其中每个ij都在1和n之间,并且1<=i1<i2<...<ik>=n,子序列不是子串,并不要求连续。例如zxyxyz和xyyzx的最长公共子序列为xyyz。
此问题可以用动态规划技术来解决,为了使用动态规划,首先得有一个递推公式。令A = a1a2...an好B = b1b2...bn,令L[i,j]表示a1a2...ai和b1b2...bi的最长公共子序列的长度。i、j可能为0,即表示空串。则i=0或j=0时,L[i,j]=0。递推关系如下:
如果i和j都大于0,那么
- 若ai = bj,L[i,j] = L[i-1,j-1]+1
- 若ai ≠ bj,L[i,j] = max{L[i,j-1],L[i-1,j]}
根据上述递推关系可以导出如下的算法:
算法:LCS
输入:字符串A和B,长度分别为n和m
输出:A和B最长公共子序列的长度和其中一个最长公共子序列
for i ← 0 to n:
L[i,0] ← 0
end for
for j ← 0 to n:
L[0,j] ← 0
end for
for i ← 1 to n:
for j ← 1 to m:
if ai == bi then L[i,j] ← L[i-1,j-1] + 1
else L[i,j] ← max{L[i,j-1],L[i-1,j]}
end if
end for
end for
while i <= n and j <= m:
if ai == bi then 输出ai i=i+1 j=j+1
else if L[i+1,j] > L[i][j+1] then i = i+1
else j = j+1
end while
return L[n,m]
下面是C++版本的实现:
//main.cpp
#include <iostream>
#include "LCSString.h"
using std::cout;
using std::endl;
int main(void) {
LCSString s1("xyxxzxyzxy");
std::string s2("zxzyyzxxyxxz");
std::string s = s1.getLCS(s2);
cout << s1 << "和" << s2 << "的一个最长公共子序列为:";
cout << s << endl;
getchar();
return 0;
}
//LCSString.h
#pragma once
#include <string>
class LCSString:public std::string {
public:
LCSString(void);
LCSString(const char * _Ptr);
~LCSString(void);
std::string getLCS(std::string s);
};
//LCSString.cpp
#include "LCSString.h"
#include <iostream>
using std::cout;
using std::endl;
LCSString::LCSString(void):std::string() {
}
LCSString::LCSString(const char * _Ptr):std::string(_Ptr) {
}
LCSString::~LCSString(void) {
}
//求本字符串与另一个字符串s的最长公共子序列
std::string LCSString::getLCS(std::string s) {
std::string result;
int n_len = this->length()+1;
int m_len = s.length()+1;
int ** L = new int * [n_len];
for (int i = 0; i < n_len; i++) {
L[i] = new int [m_len];
}
for (int i = 0; i < n_len; i++) {
L[i][0] = 0;
}
for (int i = 0; i < m_len; i++) {
L[0][i] = 0;
}
for (int i = 1; i < n_len; i++) {
for (int j = 1;j < m_len; j ++) {
if (this->operator[](i-1) == s[j-1]) {
L[i][j] = L[i-1][j-1] + 1;
} else {
//L[i][j]取L[i][j-1]和L[i-1][j]的最大值
L[i][j] = (L[i][j-1] > L[i-1][j]?L[i][j-1]:L[i-1][j]);
}
}
}
for (int i = 0; i < n_len; i++) {
for (int j = 0; j < m_len; j++) {
cout << L[i][j] << " ";
}
cout << endl;
}
int i = n_len - 1;
int j = m_len - 1;
while (i > 0 && j > 0) {
if (this->operator[](i-1) == s[j-1]) {
result = s[j-1] + result;
i --;
j --;
} else if (L[i-1][j] == L[i][j-1]) {
i --;
} else {
j --;
}
}
for (int i = 0; i < n_len; i++) {
delete [] L[i];
}
delete [] L;
return result;
}
下面是Java版本实现:
package lcs;
public class LCSString {
private String s1;
public LCSString(String s) {
this.s1 = new String(s);
}
public String getLCSString(String s2) {
String result = new String();
int n = s1.length()+1;
int m = s2.length()+1;
int [][] L = new int [n][m];
for (int i = 0; i < n; i++) {
L[i][0] = 0;
}
for (int i = 0; i < m; i++) {
L[0][i]= 0;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
L[i][j]= L[i-1][j-1] + 1;
} else {
//L[i][j]取L[i][j-1]和L[i-1][j]的最大值
L[i][j] = (L[i][j-1] > L[i-1][j]?L[i][j-1]:L[i-1][j]);
}
}
}
int i = n - 1;
int j = m - 1;
while (i > 0 && j > 0) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
result = s1.charAt(i-1) + result;
i --;
j --;
} else if (L[i-1][j] == L[i][j-1]) {
i --;
} else {
j --;
}
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1 = "xyxxzxyzxy";
String s2 = "zxzyyzxxyxxz";
LCSString lcs = new LCSString(s1);
System.out.println(s1 + "和" + s2 + "的一个最长公共子序列为:" + lcs.getLCSString(s2));
}
}
下面是Python版本实现:
#! /usr/bin/env python
# -*- coding:utf-8 -*-
class LCSString:
def __init__(self, s):
self.s1 = str(s)
def getLCSString(self, s2):
result = ''
n = len(self.s1)+1
m = len(s2)+1
L = [0]*n
for i in range(0, n):
L[i] = [0] * m
for i in range(1, n):
for j in range(1, m):
if self.s1[i-1] == s2[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
print
for i in L:
for j in i:
print j,
print
i = n-1
j = m-1
while i > 0 and j > 0:
if self.s1[i-1] == s2[j-1]:
result = s2[j-1] + result
i -= 1
j -= 1
elif L[i-1][j] == L[i][j-1]:
i -= 1
else:
j -= 1
return result
if __name__ == '__main__':
s1 = "xyxxzxyzxy"
s2 = "zxzyyzxxyxxz"
lcs = LCSString(s1)
print s1 + "和" + s2 + "的一个最长公共子序列为:" + lcs.getLCSString(s2)
分享到:
相关推荐
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
最长公共子序列问题 最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含...
由此函数,把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段,第1阶段,按照式1计算X1和Yj的最长公共子序列长度L[1][j](1),第2阶段,按照2式计算X2和Yj的最长公共子序列长度L[2][j](1),...
C++求最长公共子序列!实用 花费了好长时间!!
算法导论实验 最长公共子序列程序源码 实验报告
最长公共子序列的算法实现,采用递归方法。
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
用Python实现动态规划中最长公共子序列和最长公共子串问题!
最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
实现了求最长公共子序列的算法,内容简单易懂,代码也很短