Java算法之最长公共子序列问题(LCS)实例分析
作者:萌神哆啦A梦 发布时间:2022-12-06 08:31:42
本文实例讲述了Java算法之最长公共子序列问题(LCS)。分享给大家供大家参考,具体如下:
问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X= { x1, x2,…, xm},则另一序列Z= {z1, z2,…, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,…, ik},使得对于所有j=1,2,…,k有 Xij=Zj。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X= { A, B, C, B, D, A, B}和Y= {B, D, C, A, B, A},则序列{B,C,A}是X和Y的一个公共子序列,序列{B,C,B,A}也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。给定两个序列X= {x1, x2, …, xm}和Y= {y1, y2, … , yn},要求找出X和Y的一个最长公共子序列。
问题解析:设X= { A, B, C, B, D, A, B},Y= {B, D, C, A, B, A}。求X,Y的最长公共子序列最容易想到的方法是穷举法。对X的多有子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列。由集合的性质知,元素为m的集合共有2^m个不同子序列,因此,穷举法需要指数级别的运算时间。进一步分解问题特性,最长公共子序列问题实际上具有最优子结构性质。
设序列X={x1,x2,……xm}和Y={y1,y2,……yn}的最长公共子序列为Z={z1,z2,……zk}。则有:
(1)若xm=yn,则zk=xm=yn,且zk-1是Xm-1和Yn-1的最长公共子序列。
(2)若xm!=yn且zk!=xm,则Z是Xm-1和Y的最长公共子序列。
(3)若xm!=yn且zk!=yn,则Z是X和Yn-1的最长公共子序列。
其中,Xm-1={x1,x2……xm-1},Yn-1={y1,y2……yn-1},Zk-1={z1,z2……zk-1}。
递推关系:用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中,Xi={x1,x2……xi},Yj={y1,y2……yj}。当i=0或j=0时,空序列是xi和yj的最长公共子序列。此时,c[i][j]=0;当i,j>0,xi=yj时,c[i][j]=c[i-1][j-1]+1;当i,j>0,xi!=yj时,
c[i][j]=max{c[i][j-1],c[i-1][j]},由此建立递推关系如下:
构造最优解:由以上分析可知,要找出X={x1,x2,……xm}和Y={y1,y2,……yn}的最长公共子序列,可以按一下方式递归进行:当xm=yn时,找出xm-1和yn-1的最长公共子序列,然后在尾部加上xm(=yn)即可得X和Y的最长公共子序列。当Xm!=Yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者为X和Y的最长公共子序列。设数组b[i][j]记录c[i][j]的值由哪一个子问题的解得到的,从b[m][n]开始,依其值在数组b中搜索,当b[i][j]=1时,表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列。当b[i][j]=2时,表示Xi和Yj的最长公共子序列与Xi-1和Yj-1的最长公共子序列相同。当b[i][j]=3时,表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。
代码如下:
package LCS;
public class LCS {
public static int[][] LCSLength ( String[] x, String[] y) {
int m = x.length;
int n = y.length;
int[][] b = new int[x.length][y.length];
int[][] c = new int[x.length][y.length];
for(int i = 1; i < m; i++) {
c[i][0] = 0;
}
for(int i = 1; i < n; i++) {
c[0][i] = 0;
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(x[i] == y[j]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1]) {
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else {
c[i][j] = c[i][j-1];
b[i][j]=3;
}
}
}
return b;
}
public static void LCS(int[][] b, String[] x, int i, int j) {
if(i == 0|| j == 0) return;
if(b[i][j] == 1) {
LCS(b,x,i - 1, j - 1);
System.out.print(x[i] + " ");
}
else if(b[i][j] == 2) {
LCS(b,x,i - 1, j);
}
else LCS(b,x,i, j-1);
}
public static void main(String args[]) {
System.out.println("脚本之家测试结果:");
String[] x = {" ","A", "B", "C", "B", "D", "A", "B"};
String[] y = {" ","B", "D", "C", "A", "B", "A"};
int[][] b = LCSLength(x, y);
System.out.println("X和y的最长公共子序列是:");
LCS(b, x, x.length - 1, y.length - 1);
}
}
运行结果:
希望本文所述对大家java程序设计有所帮助。
来源:http://blog.csdn.net/u014755255/article/details/50571192
猜你喜欢
- 前言在实现红黑树之前,我们先来了解一下符号表。符号表的描述借鉴了Algorithms第四版,详情在:https://algs4.cs.pri
- 一、进程线和程的概念线程: 一个线程是一个独立的执行流,每个线程之间都可以按照顺讯执行自己的代码. 多个线程之间 “同时
- 前言我相信很多Android开发同学都遇到过这样的需求: 1.实现一个Splash界面,界面上有应用相关的背景图片和一个开始按钮.
- java与JSON数据的转换实例详解JSON与JAVA数据的转换(JSON 即 JavaScript Object Natation,它是一
- 前言Spring动态配置多数据源,即在大型应用中对数据进行切分,并且采用多个数据库实例进行管理,这样可以有效提高系统的水平伸缩性。而这样的方
- package com.infomorrow.parser_report;import org.junit.Test;public clas
- 介绍try-with-resources是Java中的环绕语句之一,旨在减轻开发人员释放try块中使用的资源的义务。它最初在Java 7中引
- 本文实例为大家分享了java使用HashMap实现斗地主的具体代码,供大家参考,具体内容如下案例介绍按照斗地主的规则,完成洗牌发牌的动作。
- 1. 准备工作需要提前安装好Elasticsearch,访问地址:http://127.0.0.1:9200/ 得到以下结果,得到clust
- SSM Mapper查询出返回数据查不到个别字段原因开启了驼峰命名法则,Bean里的字段不识别_注释掉或者把实体类里的字段_去掉换位大写SS
- 绪论转眼间,2016伴随着互联网寒冬和帝都的雾霾马上就过去了,不知道大家今年一整年过得怎么样?最近票圈被各个城市的雾霾刷屏,内心难免会动荡,
- 开始 在本文中,我将展示如何使用各种不同的 Java 技术构建一些简单的 Comet 风格的 Web 应
- 一、网络爬虫的基本知识网络爬虫通过遍历互联网络,把网络中的相关网页全部抓取过来,这体现了爬的概念。爬虫如何遍历网络呢,互联网可以看做是一张大
- 概述Spring boot 中的 @Conditional 注解是一个不太常用到的注解,但确实非常的有用,我们知道 Spring Boot
- mybatis if传入字符串数字踩坑前台页面内容,注意这里的类型为字符串类型的数字<li>  
- 首先,确保 IDEA 软件正确安装完成,Java 开发工具包 JDK 安装完成。IDEA 的 Java 项目 (Project) 则相当于
- final——final用于类表示该类不能派生子类。final用于方法表示该方法不能被子类重写。final用于变量时表示常量,类似于C/C+
- Java 中的运算符与 C 语言基本一致。1、算术运算符操作符描述例子+加法 : 相加运算符两侧的值A + B 等于 30-减法 : 左操作
- 本文实例为大家分享了Unity3D选择本地图片并加载的具体代码,供大家参考,具体内容如下①找到System.Windows.Forms.dl
- 前言需求是上传Excel文件并读取Excel文件中的内容,根据获取的数据执行完某些业务操作后再将一些数据写回到excel中。前台使用Form