文档章节

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

zcmyworld
 zcmyworld
发布于 2015/08/24 20:48
字数 1101
阅读 59
收藏 0
点赞 0
评论 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
广州
动态规划与贪心算法

动态规划 基本概念 和分治法一样,动态规划(dynamic programming)是通过组合子问题的解而解决整个问题的。分治法是指将问题划分成一些独立地子问题,递归地求解各子问题,然后合并子问题的...

heartfly ⋅ 2010/10/04 ⋅ 0

开源书籍-JavaScript 编程精解

《JavaScript 编程精解》(Eloquent JavaScript)第三版,是由马尔奇·哈弗贝克(Marlin Haverbeke)JavaScript程序员编写的JS入门书籍,Marlin Haverbeke通晓多种编程语言,在Web开发方面积累...

marsdream ⋅ 06/04 ⋅ 0

太原面经分享:如何用js实现返回斐波那契数列的第n个值的函数

面试攒经验,let's go! 值此高考来临之际,闲不住的我又双叒叕出发去面试攒经验了,去了公司交待一番流程后,面试官甩给了我一张A4纸,上面写着一道js算法笔试题(一开始我并不知道这是在考...

闰土大叔 ⋅ 06/07 ⋅ 0

以变制变——前端动态化代码保护方案探索

欢迎大家前往腾讯云+社区,获取更多腾讯海量技术实践干货哦~ 本文分享了腾讯防水墙团队关于机器对抗的动态化思路,希望能抛砖引玉,给现在正在做人机对抗的团队一些启发,帮助更多中小型公司...

腾讯云加社区 ⋅ 06/07 ⋅ 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

Lynx技术分析-JS引擎扩展设计

JS Binding 技术 Lynx(一个高效的跨平台框架) 的 JS Binding 技术最主要的目的是搭建一个高效的与 JS 引擎解耦的通信桥梁,同时具备 JS 引擎切换的能力。该技术经历了多次迭代,最终通过抽...

hxxft ⋅ 05/15 ⋅ 0

【回放视频+PPT下载整理】编程语言系列讲座:深度学习JavaScript和React技术

编程语言系列讲座JavaScript篇,我们邀请了行业资深专家靖鑫和逸翾与大家一起学习最流行的编程语言,本次系列直播将对于JavaScript中的对象、函数和异步编程进行详细解读,并带领大家学习Rea...

云迹九州 ⋅ 04/29 ⋅ 0

JavaScript 中常见设计模式-单例模式

     单例模式两个条件   确保只有一个实例   可以全局访问   适用   适用于弹框的实现,全局缓存   实现单例模式      JavaScript 中的单例模式   因为 JavaScript 是无...

webstack前端栈 ⋅ 05/19 ⋅ 0

JavaScript 和服务器端方向推荐书单(附简评)

我一直以来读书是获取知识最好的方式,很长时间以来,我都在博客维护了一个 推荐书单,最近又做了一些整理,为每本书都添加了简评,希望能对大家有帮助,当然如果能用我的推广链接购书就再好...

eapxuo ⋅ 02/09 ⋅ 0

JavaScript 算法与数据结构 - javascript-algorithms

javascript-algorithms 包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中...

匿名 ⋅ 05/31 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

骰子游戏代码开源地址

因为阿里云现在服务器已经停用了,所以上面的配置已经失效。 服务端开源地址:https://gitee.com/goalya/chat4.git 客户端开源地址:https://gitee.com/goalya/client4.git 具体运行界面请参考...

算法之名 ⋅ 38分钟前 ⋅ 0

设计模式--装饰者模式

装饰者模式 定义 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比生成子类更为灵活。 通用类图 意图 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比...

gaob2001 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部