文档章节

动态规划算法解LCS问题的JS实践

zcmyworld
 zcmyworld
发布于 2015/08/24 20:48
字数 1101
阅读 75
收藏 0

LCS (最长公共子序列)

定义:一个数列 S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

如有两个字符串:1235和136,则:

1, 12, 123, 1235, 2, 23, ..., 1235是字符串1235的子序列

1, 3, 13, 36, ..., 136是136的子序列

13是1235和136的最长公共子序列

LCS问题即求两集合最长公共子序列的问题

理论基础

设有:

Xi=﹤x1,⋯,xi﹥即X序列的前i个字符 (1≤i≤m)(前缀)

Yj=﹤y1,⋯,yj﹥即Y序列的前j个字符 (1≤j≤n)(前缀)

注:X和Y是从1开始算起

假定Z=﹤z1,⋯,zk﹥∈LCS(X , Y)。

即Z为Xi和Yj的最长公共子序列

  • 若zm=zn(最后一个字符相同),则:该字符必是x与y的任一最长公共子序列Z(设长度为k)的最后一个字符

  • 若zm≠zn,则Zk要么属于ym-1,要么属于yn-1

设Xi和Yj最长公共子序列的长度为C[i,j],则有(公式1):

  • c[i, j] = 0 //when i = 0 or j = 0

  • C[i, j] = c[i - 1, j - 1] + 1; //when zm = zn

  • c[i, j] = max(c[i, j - 1], c[i - 1, j]) //when zm ≠ zn

那么,接下来的目标就是,想办法判断子序列的最后一个字符是只属于X序列还是只属于Y序列,还是属于X序列和Y序列。

而当c[i,j-1] > c[i-1,j]的时候,最长子序列的最后一个字符存在于xi中,反之,存在于yj中

以序列 X:1235 和 Y:136 为例,根据公式1,可以得出以下表格(图1):

举例来说,当x为5,y为6时,序列1235和136的最长公共子序列长度为2;

当x为2,y为3时,序列12和13的最长公共子序列长度为1。

因为存在 c[i, j] = c[i - 1, j - 1] + 1 这样的运算,如果数组以0为开头,会出现下标为-1的情况,所以将表格改变为如下形式,x行和x列没有实际意义:

JavaScript代码以数组的形式生成以上表格的代码如下:

    var arr = [];    //array init
    for (var i = 0; i < str1.length + 1; i++) {
        arr[i] = [];        for (var j = 0; j < str2.length + 1; j++) {
            arr[i][j] = 0;            
        }
    }    
    for (var i = 1; i < str1.length + 1; i++) {        
            for (var j = 1; j < str2.length + 1; j++) {            
            if (str1[i - 1] == str2[j - 1]) {
                arr[i][j] =  arr[i - 1][j - 1] + 1;
            } else if (arr[i - 1][j] >= arr[i][j - 1]) {
                arr[i][j] = arr[i - 1][j];
            } else {
                arr[i][j] = arr[i][j - 1];
            }
        }
    }
接下来,根据这个表格去计算出最长公共子序列

首先以序列X的最后一个字符5和Y的最后一个字符6进行比较,

i为4,j为3,长度为c[4,3]=2,5≠6,又因为c[4,2]=c[3,3],再以c[4,2]开始进行比较

i为3,j为3,长度为c[4,2]=2,5≠3,又因为c[4,2]<c[3,2],再以c[3,2]开始进行比较

...

蓝色部分为比较时经过的路径,最后得出1,3最长公共子序列

JavaScript实现代码为:

    function _lcs(str1, str2, i, j, arr, result) {        
        if (i == 0 || j == 0) {            
           return;
        }         
        if (str1[i - 1] == str2[j - 1]) {
            _lcs(str1, str2, i - 1, j - 1, arr, result);
            result.push(str1[i - 1]);
        } else if (arr[i][j - 1] >= arr[i - 1][j]) {
            _lcs(str1, str2, i, j - 1, arr, result);
        } else {
            _lcs(str1, str2, i - 1, j, arr, result);
        }
    }

最后,完整的实验代码是:

    function lcs(str1, str2) {    
        var arr = [];    //array init
        for (var i = 0; i < str1.length + 1; i++) {
            arr[i] = [];        
            for (var j = 0; j < str2.length + 1; j++) {
                arr[i][j] = 0;            
            }
        }    
        for (var i = 1; i < str1.length + 1; i++) {        
            for (var j = 1; j < str2.length + 1; j++) {            
                if (str1[i - 1] == str2[j - 1]) {
                    arr[i][j] =  arr[i - 1][j - 1] + 1;
                } else if (arr[i - 1][j] >= arr[i][j - 1]) {
                    arr[i][j] = arr[i - 1][j];
                } else {
                    arr[i][j] = arr[i][j - 1];
                }
            }
        }    
        var result = [];
        _lcs(str1, str2, str1.length, str2.length, arr, result);    
        console.log(result)
    }
    
    function _lcs(str1, str2, i, j, arr, result) {    
        if (i == 0 || j == 0) {        
            return;
        }    
        if (str1[i - 1] == str2[j - 1]) {
            _lcs(str1, str2, i - 1, j - 1, arr, result);
            result.push(str1[i - 1]);
        } else if (arr[i][j - 1] >= arr[i - 1][j]) {
            _lcs(str1, str2, i, j - 1, arr, result);
        } else {
            _lcs(str1, str2, i - 1, j, arr, result);
        }
    }

        测试:

    var str1 = "asdfg29hj40kl";    var str2 = "qw29e4r0tyuiop";
    lcs(str1, str2);

输出:

    [ '2', '9', '4', '0' ]

以上。



个人博客原文链接:http://www.zcmyworld.com/singleArticle?articleId=334

© 著作权归作者所有

共有 人打赏支持
zcmyworld
粉丝 0
博文 1
码字总数 1101
作品 0
广州
私信 提问
腾讯移动前端框架 mt 2.0 发布

MT是手机腾讯网前端团队开发维护的一个专注于移动端的js模块管理框架。 Git:http://git.oschina.net/luyongfugx/mt mt介绍文档:http://mt.tencent.com/mt1index.html 为什么使用MT 无更新不...

oschina
2014/06/11
8.7K
21
使用动态规划 实现字符级Diff & Patch

文章开头先上demo,只需键入任意内容的两个字符串,页面上就能自动计算并呈现字符串之间的差分。 demo地址:string-diff-demo.herokuapp.com 源码地址:github.com/lqt0223/str… 动态规划 ...

lqt0223
02/13
0
0
手机腾讯网mt框架之mtwebapp示例解析。

手机腾讯网mt2.0框架发布有一段时间,但是经常有朋友问怎么用,其实项目里面是有一个基于jqmobi和ratchet的webapp示例的,这里我们就来分析一下。代码目录在:https://github.com/mtjs/mt/tr...

卢勇福
2014/11/12
0
10
[JS进阶] 编写可维护性代码

1 可维护性代码的特点 可理解性:其他人可以接手代码并理解它的意图,无需原开发人员花太多时间解释! 直观性:代码中的东西一看就能明白,尽管其操作过程复杂。 可适应性:代码以一种数据上...

赵小宾
2015/04/01
0
0
常用算法和复杂度总结

一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) 合并排序 MergeSort(A,p,r) O(nlog n) 选最大 FindMax O(n) 选最...

啊莱
2010/01/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

解析JQuery中each方法的使用

each() 方法规定为每个匹配元素规定运行的函数。写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 概述: each() 方法规定为每个匹配...

前端攻城小牛
16分钟前
3
0
深入解析Vue开发动态刷新Echarts组件的教程

需求背景:dashboard作为目前企业中后台产品的“门面”,如何更加实时、高效、炫酷的对统计数据进行展示,是值得前端开发工程师和UI设计师共同思考的一个问题。今天就从0开始,封装一个动态渲...

peakedness丶
29分钟前
3
0
memcached

memcached 为了避免内存碎片化(传统的内存管理方式是,使用完通过malloc分配的内存后通过free来回收内存,这种方式容易产生内存碎片并降低操作系统对内存的管理效率),采用了 slab allocatio...

Cobbage
29分钟前
3
0
keepalived的介绍及配置高可用集群

12月19日任务 18.1 集群介绍 18.2 keepalived介绍 18.3/18.4/18.5 用keepalived配置高可用集群 集群介绍 根据功能划分为2类:高可用和负载均衡 高可用集群:通常为两台服务器,一台工作,另外...

robertt15
30分钟前
5
0
WiFi攻击的三种方式

导读 WiFi的安全问题已经引起了不少的使用者重视,甚至已经出现草木皆兵的现象。那么黑客到底是如何做到绕过身份验证来获取WiFi使用权的呢?主要有以下三种方式,其中最后一种方式十分简单。 ...

问题终结者
44分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部