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

介绍

最长公共子序列(LCS)是从两个给定的序列X和Y中提取尽可能多的字符，并根据它们在原始序列中的排列顺序来排列它们。LCS问题的算法被广泛使用。比如在不同版本软件的管理中，利用LCS算法发现新旧版本的异同；在软件测试中，LCS算法用于比较录制和播放的序列。在基因工程领域，使用LCS算法检查患者DNA链和健康DNA链的异同在反剽窃系统中，使用LCS算法检查论文的抄袭率。LCS算法还可以用于程序代码相似性度量、人体跑步序列检索、视频片段匹配等，因此对LCS算法的研究具有很高的应用价值。

基本概念

子序列：特定序列的子序列是在给定序列中移除零个或多个元素的结果(不改变元素之间的相对顺序)。比如序列A、B、C、B、D、A、B、C、A、B、C、A、B、C、D、A等的子序列。

公共子序列：给定序列x和Y，如果序列z是x和Y的子序列，那么z是x和Y的公共子序列.X=[A，B，C，B，D，A，B]，y=[b，D，C，A，B，a]，那么序列Z=[B，C，A]就是x和y的公共子序列，它的长度是3。但z不是x和y的最长公共子序列，序列[B，C，B，A]和[B，D，A，B]也是长度为4的x和y的最长公共子序列，而x和y没有长度大于等于5的公共子序列。序列[A，B，C]和序列[E，F，G]的公共子序列只有一个空序列[]。

最长公共子序列：给定序列X和Y，从它们所有的公共子序列中选择最长的一个或几个。子串：由从前面、最后或同时删除零个或几个字符组成的新序列。与子序列不同，子序列可以从中间挑出字符。字符串cnblogs中有多少个子序列？显然有27个，比如cb，cgs等等，都是它们的子序列

再举个图解释一下：

我们可以看到，子序列不一定是连续的，但是子序列是连续的。

问题分析

我们从一个矩阵开始，自己推导状态转移方程。

首先，我们把问题转化为前端熟悉的概念。我们可以把它看作一个数组或字符串，而不是按顺序调用。一切都很简单，让我们估计并识别两个字符串进行比较。

我们注意到“子序列”的概念，它可以删除许多或零个或杀死所有子序列。此时，我们的第一个子序列是一个空字符串(如果我们的序列不是字符串，我们仍然可以)！这是真的一定要注意的！很多人就是看不懂《算法导论》的图表，很多博主也假装看不懂。我们总是从左到右比较。当然，第一个字符串是垂直放置的，因为它像矩阵一样高。

X '' B D C A B A '' A B C D A B假序x=' ABCD ab '，y=' bdc ABA '，分别取出最短序列，即空字符串与空字符串比较。LCS方程是用数字解的，所以这张表只能用数字来填充。两个空字符串的公共区域的长度为0。

X '' B D C A B A '' 0 A B C D A B然后我们不移动x，继续让空字符串出来，y让“B”出来，很明显，它们的公共区域的长度是0。y被改成其他字符，d啊，c啊，或者是他们连续组合的DC和DDC，情况保持不变，依然为0。因此，第一行是0

x ' ' b d c a b a ' ' 0 000 000 a 0 b0c 0d 0 b 0 LCS问题和背包问题有点不一样，背包问题也可以用-1行设置，而最长的公共子序列因为空序列的出现，在开始的时候已经固定了左侧和顶部。

那我们就把问题放大。这一次，双方都给出了一个人物。显然，只有当两者相同时，才能有一个不是空字符串的公共子序列，长度理解为1。

a是“x ”, y是“BDCA”的任何一个子序列

x ' ' b d c a b a ' ' 0 000 000 a 0 000 1 b 0 c 0d 0 b 0继续填写右边的空格。我应该如何填写？显然，LCS不能大于x的长度，与B的A序列相比，从A字符串开始的Y的子序列可以等于1。

x ' ' b d c a b a ' ' 0 000 000 a 0 000 11 b 0 c 0d 0 a 0 b 0如果x只发送前两个字符a和b，也就是"、" a "、" b "和" a b "，前两个已经解释过了。然后我们来看b，${X_1}==${Y_0}。我们有一个新的公共子串，应该加1。为什么呢？因为我们的矩阵是一个状态表，描述了状态从左到右，从上到下的转变过程，这些状态是基于现有的状态进行累加的。我们现在需要确认的是我们现在要填充的网格的值和它周围已经填充的网格的值之间的关系。目前信息太少，是一个孤立点。直接填写1。

x ' ' B D c A B A ' ' 0 000 000 A 0 000 11 B 0 1 c 0D 0 A 0 B 0然后我们让y多一个D作为帮手，{ ' '，A，B，AB} vs { ' '，B，D，BD}，很明显，继续填写1。直到y的第二个b，都是1。因为当它们到达BDCAB时，它们有另一个共同的子序列，AB。

x ' ' b d c a b a ' ' 0 000 000 a 0 000 11 b 0 1 1 2 c 0d 0 a 0 b 0到了这一步，我们可以总结一些规则，然后通过计算来验证我们的想法，并添加新的规则或限制来改进它们。

y将所有字符发送上去，X仍然是2个字符。经过仔细观察，2。

看五行，x再发一个c，ABC的子序列集比AB的子序列集大，所以比Y的子序列集大，即使不大，也不能比原来的小。显然新加的C不可能是战力，也不是两者的共性，所以值应该等于AB的子序列集。

“b d c a b a”0 000 000 a 0 000 11 b 0 1 1 2 c 0 1d 0 a 0 b 0并且我们可以确认，如果两个字符串之间要比较的字符不同，那么要填充的网格与其左侧或上侧相关，将采用较大的一个。

如果要比较的字符相同，不用担心，只是X的C应该和Y的C进行比较，也就是ABC的子序列集{ ' '，A，B，C，AB，BC，ABC}和BDC的子序列集{ ' '，B，D，C，BD，DC，BDC}进行比较，常见的子串是""，此时和前面的结论是一样的。当字符相等时，其对应的网格值等于左、右、左上角，左、上、左上始终相等。这些奥秘需要更严谨的数学知识来论证。

假设有A和B两个数组，A[i]是A的第I个元素，A(i)是A的第I个元素到第I个元素组成的前缀，M(i，j)是A(i)和B(j)最长的公共子序列长度。

由于算法本身的递归性质，事实上，只要它被证明，对于某个I和J:

M(i，j)=m(i-1，j-1) 1(当A[i]=B[j])

M(i，j)=max(m(i-1，j)，m(i，j-1))(当A[i]！=B[j])

第一个公式证明得很好，即当A[i]=B[j]时。通过假设m(i，j) m(i-1，j-1) 1 (m(i，j)不能小于m(i-1，j-1) 1，原因显而易见)，则可以推导出m(i-1，j-1)不是最长的矛盾结果。

第二个有一些技巧。当A[我]！当=B[j]时，仍然是反证，假设m(i，j) max(m(i-1，j)，m(i，j-1))。

根据与此相反的假设，可以得到m(i，j) m(i-1，j)。可以推导出A[i]一定在对应m(i，j)的LCS序列中(可以证明是相反的)。因为我！=B[j]，所以B[j]一定不在m(i，j)对应的LCS序列中。因此，可以推导出m(i，j)=m(i，j-1)。这导致了一个与假设相矛盾的结果。

拿到证书。

现在我们继续用下面的等式填写表格。

程序实现

//由斯图亚特梅铮函数LCS (str 1，str 2){ var row=str 1。拆分(“”)行。unstiff(')var cols=str 2。拆分(')列。unstiff(')var m=row。长度变量n=cols。长度I米；I){ DP[I]=[]for(var j=0；j n；j){ if(I===0 | | j==0){ DP[I][j]=0 continue } if(row[I]==cols[j]){ DP[I][j]=DP[I-1][j-1][j]，dp[i][j-1]) //左侧取上侧最大值}} Console.log (DP [I]。join(' ')//Debug } return DP[I-1][j-1]} LCS可以进一步简化，只要通过移动位置省略即可。

//由斯图亚特梅铮函数LCS (str 1，str 2) {var m=str 1。lengthvar n=字符串2。length var DP=[新数组(n ^ 1)。fill(0)]//第一行全部为0(var I=1；I=m；I ){ //有m ^ 1行dp[i]=[0] //第一列全部为0(var j=1；j=n；J){//if(str1[I-1]==STR 2[J-1])有n个1列{//注意STR 1的第一个字符在第二列，所以应该减1。STR 2与DP [I] [J]=DP [I-1] [J-1]相同，打印LCS

我们再给打印功能，先看看怎么打印一个。我们从右下角开始，找到顶线终止。因此，目标字符串的构造是相反的。为了避免使用stringBuffer这样麻烦的中间量，我们可以递归实现。每次执行程序，只返回一个字符串，否则返回一个空字符串，我们需要的字符串可以通过添加printLCS(x，y，)str[i]。

让我们写另一个方法来验证我们得到的字符串是否是真正的LCS字符串。作为一个已经工作过的人，不会写的代码就跟在校学生一样，让别人不用单元测试就能踩线。

//由si梅铮，打印一个LCS函数打印LCS (DP，str 1，str 2，I，j){ if(I==0 | | j==0){ return“”；} if(str1[i-1]==str2[j-1]){ return printLCS(DP，str 1，str 2，I-1，j-1)str 1[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)；} } }//由Situ梅铮，将目标字符串转换成正则，并验证是否是LCS函数validate LCS (EL，STR1，STR2) {var re=new regexp (EL。拆分(“”)。join('。*)控制台. log (EL，Re。测试(str 1)，re。测试(str 2))返回环。测试(str 1)环。测试(str 2)}使用：

函数LCS(str1，str 2){ var m=str 1。长度变量n=字符串2。长度/.略，自行补充var s=printLCS(dp，str1，str2，m，n)validate cs(s，str1，str2)返回C1=LCS(' abcdab '，' BDCABA ')；console.log(c1) //4 BCBA、BCAB、BDABvar c2=LCS('13456778 '，' 357486782 ')；控制台。log(C2)//5 34678 var C3=LCS(' accggtcgagggcaagcgccgaa '，' gtcgttcggaatgccgtcttgtaaa ')；控制台。日志(C3)//20 gtcgtcggaagccgcgaa(9503 . 163.com)

打印全部松散耦合系统

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

//由司徒正美打印所有LCS函数printal LCS(DP，str1，str2，I，j){ if(I==0 | | j==0)}返回新的Set([' '])} else if(str1[i-1]==str2[j-1]){ var newSet=new Set()printal LCS(DP，str 1，str 2，I-1，j-1).forEach(function(El){ newSet。add(El str1[I-1]))})返回newSet } else { var Set=new Set()if(DP[I][j-1]=DP[I-1][j]){ printal cs(DP，str 1，str2，I，j-1).函数集。add(El)})} if(DP[I-1][j]=DP[I][j-1]){//必须用=,不能简单一个其他搞定LCS印刷公司(DP，str1，str2，i-1，j).函数集。add(El)})} return set } }使用：

函数LCS(str1，str 2){ var m=str 1。长度变量n=字符串2。长度/.略，自行补充var s=printal cs(DP，str1，str2，m，n)控制台。log s . foreach(function(El){ validateLCS(El，str1，str2) console.log('输出LCS，埃尔)})返回C1=LCS(' abcdab '，' BDCABA ')；console.log(c1) //4 BCBA、BCAB、BDABvar c2=LCS('13456778 '，' 357486782 ')；控制台。log(C2)//5 34678 var C3=LCS(' accggtcgagggcaagcgccgaa '，' gtcgttcggaatgccgtcttgtaaa ')；控制台。日志(C3)//20 gtcgtcggaagccgcgaa(9504 . 163.com)

空间优化

使用滚动数组：

函数LCS(str1，str 2){ var m=str 1。长度变量n=字符串2。长度var DP=[新数组(^ 1号法律公告).填充(0)]，现在=1，行/第一行全是0表示(var I=1；I=m；i ){ //一共有2行row=dp[now]=[0] //第一列全是0表示(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 .}返回行？行[n]: 0}危险的递归解法

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

//警告，字符串的长度一大就会爆栈函数LCS(str1，str2，a，b){ if(a===void 0){ a=str 1。length-1 } if(b===void 0){ b=str2。length-1 } if(a==-1 | | b==-1){ return 0 } if(str 1[a]==str 2[b]){ return LCS(str 1，str 2，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)返回x=y？x : y } }参考链接

http://blog.csdn.net/hrn1216/article/details/51534607https://segmentfault.com/a/1190000002641054总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对我们的支持。