javascript实现最长公共子序列实例代码

来源：动视网责编：小采时间：2020-11-27 22:20:02

javascript实现最长公共子序列实例代码

javascript实现最长公共子序列实例代码:介绍最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。LCS问题的算法用途广泛，如在软件不同版本的管理中，用LCS算法找到新旧版本的异同处;在软件测试中，用

推荐度：

点击下载本文 文档为doc格式

导读javascript实现最长公共子序列实例代码:介绍最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。LCS问题的算法用途广泛，如在软件不同版本的管理中，用LCS算法找到新旧版本的异同处;在软件测试中，用

我们现在用下面的方程来继续填表了。

程序实现

//by 司徒正美
function LCS(str1, str2){
 var rows = str1.split("")
 rows.unshift("")
 var cols = str2.split("")
 cols.unshift("")
 var m = rows.length 
 var n = cols.length 
 var dp = []
 for(var i = 0; i < m; i++){ 
 dp[i] = []
 for(var j = 0; j < n; j++){ 
 if(i === 0 || j === 0){
 dp[i][j] = 0
 continue
 }
 
 if(rows[i] === cols[j]){ 
 dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
 }else{
 dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //对左边，上边取最大
 }
 }
 console.log(dp[i].join(""))//调试
 } 
 return dp[i-1][j-1]
 }

LCS可以进一步简化，只要通过挪位置，省去新数组的生成

//by司徒正美
function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 var dp = [new Array(n+1).fill(0)] //第一行全是0
 for(var i = 1; i <= m; i++){ //一共有m+1行
 dp[i] = [0] //第一列全是0
 for(var j = 1; j <= n; j++){//一共有n+1列
 if(str1[i-1] === str2[j-1]){ 
 //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
 dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
 } else {
 dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) 
 }
 }
 } 
 return dp[m][n];
}

打印一个LCS

我们再给出打印函数，先看如何打印一个。我们从右下角开始寻找，一直找到最上一行终止。因此目标字符串的构建是倒序。为了避免使用stringBuffer这样麻烦的中间量，我们可以通过递归实现，每次执行程序时，只返回一个字符串，没有则返回一个空字符串，以 printLCS(x,y,...) + str[i] 相加，就可以得到我们要求的字符串。

我们再写出一个方法，来验证我们得到的字符串是否真正的LCS字符串。作为一个已经工作的人，不能写的代码像在校生那样，不做单元测试就放到线上让别人踩坑。

//by 司徒正美，打印一个LCS
function printLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
 return "";
 }
 if( str1[i-1] == str2[j-1] ){
 return printLCS(dp, str1, str2, i-1, j-1) + str1[i-1];
 }else{
 if (dp[i][j-1] > dp[i-1][j]){
 return printLCS(dp, str1, str2, i, j-1);
 }else{
 return printLCS(dp, str1, str2, i-1, j);
 }
 }
}
//by司徒正美， 将目标字符串转换成正则，验证是否为之前两个字符串的LCS
function validateLCS(el, str1, str2){
 var re = new RegExp( el.split("").join(".*") )
 console.log(el, re.test(str1),re.test(str2))
 return re.test(str1) && re.test(str2)
}

使用：

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 //....略，自行补充
 var s = printLCS(dp, str1, str2, m, n)
 validateLCS(s, str1, str2)
 return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

打印全部LCS

思路与上面差不多，我们注意一下，在LCS方法有一个Math.max取值，这其实是整合了三种情况，因此可以分叉出三个字符串。我们的方法将返回一个es6集合对象，方便自动去掉。然后每次都用新的集合合并旧的集合的字任串。

//by 司徒正美 打印所有LCS
function printAllLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
 return new Set([""])
 }else if(str1[i-1] == str2[j-1]){
 var newSet = new Set()
 printAllLCS(dp, str1, str2, i-1, j-1).forEach(function(el){
 newSet.add(el + str1[i-1])
 })
 return newSet
 }else{
 var set = new Set()
 if (dp[i][j-1] >= dp[i-1][j]){
 printAllLCS(dp, str1, str2, i, j-1).forEach(function(el){
 set.add(el)
 })
 }
 if (dp[i-1][j] >= dp[i][j-1]){//必须用>=，不能简单一个else搞定
 printAllLCS(dp, str1, str2, i-1, j).forEach(function(el){
 set.add(el)
 })
 } 
 return set
 } 
 }

使用：

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 //....略，自行补充
 var s = printAllLCS(dp, str1, str2, m, n)
 console.log(s)
 s.forEach(function(el){
 validateLCS(el,str1, str2)
 console.log("

输出LCS",el) }) return dp[m][n] } var c1 = LCS( "ABCBDAB","BDCABA"); console.log(c1) //4 BCBA、BCAB、BDAB var c2 = LCS("13456778" , "357486782" ); console.log(c2) //5 34678 var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" ); console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

空间优化

使用滚动数组：

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 var dp = [new Array(n+1).fill(0)],now = 1，row //第一行全是0
 for(var i = 1; i <= m; i++){ //一共有2行
 row = dp[now] = [0] //第一列全是0
 for(var j = 1; j <= n; j++){//一共有n+1列
 if(str1[i-1] === str2[j-1]){ 
 //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
 dp[now][j] = dp[i-now][j-1] + 1 //对角＋1
 } else {
 dp[now][j] = Math.max( dp[i-now][j], dp[now][j-1]) 
 }
 }
 now = 1- now; //1-1=>0;1-0=>1; 1-1=>0 ...
 } 
 return row ? row[n]: 0
}

危险的递归解法

str1的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，str1共有${2^m}$个不同子序列（str2亦如此，如为${2^n}$），因此复杂度达到惊人的指数时间（${2^m * 2^n}$）。

//警告，字符串的长度一大就会爆栈
function LCS(str1, str2, a, b) {
 if(a === void 0){
 a = str1.length - 1
 }
 if(b === void 0){
 b = str2.length - 1
 }
 if(a == -1 || b == -1){
 return 0
 } 
 if(str1[a] == str2[b]) {
 return LCS(str1, str2, a-1, b-1)+1;
 }
 if(str1[a] != str2[b]) {
 var x = LCS(str1, str2, a, b-1)
 var y = LCS(str1, str2, a-1, b)
 return x >= y ? x : y
 }
 }

参考链接

http://blog.csdn.net/hrn1216/article/details/51534607

https://segmentfault.com/a/11900000021054

https://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html

http://www.cppblog.com/mysileng/archive/2013/05/14/200265.html

总结