文档章节

【算法导论学习-29】动态规划经典问题02:最长公共子序列问题(Longest common subsequence,LCS)

猪刚烈
 猪刚烈
发布于 2014/09/24 13:59
字数 1049
阅读 21
收藏 0

问题描述:序列X={x1,x2,…,xn},Y={y1,y2,…,yn},当Z={z1,z2…,zn}是X的严格递增下标顺序(可以不连续)的子集,也是Y的严格递增下标顺序(可以不连续)的子集,则Z是X和Y的公共子序列。例如X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},{B,C,A}、{B,C,B,A}、{B,D,A,B}都是X和Y的公共子序列。其中最长的公共子序列叫做Longest common subsequence,即经典的LCS。

  具体点:char[]xArray和char[] yArray是字符数组,长度分别为m、n,求他们的LCS

【分析】自顶向下分析,二维数组cTable[i][j]记录xArray[0~i],yArray[0~j]的最长公共子序列的长度,则cTable[m][n]记录xArray[0~m],yArray[0~n]的最长公共子序列的长度

1)   如果xArray[m]=yArray[n],表明最后一个元素xArray[m]是LCS中的元素,xArray[0~m],yArray[0~n]的最长公共子序列=xArray[0~m-1],yArray[0~n-1]的最长公共子序列+1,即cTable[m][n]=cTable[m-1][n-1]。

2)   如果xArray[m]!=yArray[n],表明xArray[m]、yArray[n]都有可能是LCS中的元素,但不能同时是。如果xArray[m]可能是,则xArray[0~m],yArray[0~n]的最长公共子序列=xArray[0~m],yArray[0~n-1]的最长公共子序列;如果yArray[n]可能是,则xArray[0~m],yArray[0~n]的最长公共子序列=xArray[0~m-1],yArray[0~n]的最长公共子序列。即cTable[m][n]=max(cTable[m-1][n], cTable[m][n-1])。

状态递归方程为:


参考《算法导论》P394页伪代码,java实现如下:

  1. /** 
  2.      * 创建时间:2014年9月3日 下午9:00:13 
  3.      * 项目名称:Test 
  4.      * @author Cao Yanfeng  Peking University
  5.      * @since JDK 1.6.0_21 
  6.      * 类说明:  最长公共子序列问题(Longest common subsequence,LCS)
  7.      */ 
  8.     public static void main(String[] args) { 
  9.         // TODO 自动生成的方法存根 
  10.         String x="ABCBDABCBACABC"
  11.         String y="BDCABACABABCB"
  12.         int temp=getLCSLength(x, y); 
  13.         System.out.println("\n长度为:"+temp); 
  14.     } 
  15.     public static int getLCSLength(String x,String y) { 
  16.         char[] xArray=x.toCharArray(); 
  17.         char[] yArray=y.toCharArray(); 
  18.         int m=xArray.length; 
  19.         int n=yArray.length; 
  20.         int [][] bTable=new int[m][n]; 
  21.         /*cTable[i][j]记录xArray[0~i],yArray[0~j]的最长公共子序列的长度*/ 
  22.         int [][] cTable=new int[m+1][n+1]; 
  23.         for (int i = 0; i <m; i++) { 
  24.             for (int j = 0; j < n; j++) { 
  25.                 if (xArray[i]==yArray[j]) { 
  26.                     cTable[i+1][j+1]=cTable[i][j]+1
  27.                     bTable[i][j]=2;//相等标记为2 
  28.                 }else if (cTable[i][j+1]>=cTable[i+1][j]) { 
  29.                     cTable[i+1][j+1]=cTable[i][j+1]; 
  30.                     bTable[i][j]=1
  31.                 }else
  32.                     cTable[i+1][j+1]=cTable[i+1][j]; 
  33.                     bTable[i][j]=3
  34.                 } 
  35.                  
  36.             } 
  37.              
  38.         } 
  39.         System.out.print("最大子数组为:"); 
  40.         printLCS(xArray, bTable, m-1,n-1); 
  41.         return cTable[m][n]; 
  42.     } 
  43.     /*输出最佳路径即最长公共子序列*/ 
  44.     public static void printLCS (char[] xArray,int[][] bTable,int i,int j) { 
  45.         if (i==-1||j==-1) { 
  46.             return
  47.         } 
  48.         if (bTable[i][j]==2) { 
  49.             printLCS(xArray, bTable, i-1, j-1); 
  50.             System.out.print(xArray[i]); 
  51.         }else if (bTable[i][j]==1) { 
  52.             printLCS(xArray, bTable, i-1, j); 
  53.         }else
  54.             printLCS(xArray, bTable, i, j-1); 
  55.         } 
  56.     } 
  57.  
/**  
	 * 创建时间:2014年9月3日 下午9:00:13  
	 * 项目名称:Test  
	 * @author Cao Yanfeng  Peking University
	 * @since JDK 1.6.0_21  
	 * 类说明:  最长公共子序列问题(Longest common subsequence,LCS)
	 */
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		String x="ABCBDABCBACABC";
		String y="BDCABACABABCB";
		int temp=getLCSLength(x, y);
		System.out.println("\n长度为:"+temp);
	}
	public static int getLCSLength(String x,String y) {
		char[] xArray=x.toCharArray();
		char[] yArray=y.toCharArray();
		int m=xArray.length;
		int n=yArray.length;
		int [][] bTable=new int[m][n];
		/*cTable[i][j]记录xArray[0~i],yArray[0~j]的最长公共子序列的长度*/
		int [][] cTable=new int[m+1][n+1];
		for (int i = 0; i <m; i++) {
			for (int j = 0; j < n; j++) {
				if (xArray[i]==yArray[j]) {
					cTable[i+1][j+1]=cTable[i][j]+1;
					bTable[i][j]=2;//相等标记为2
				}else if (cTable[i][j+1]>=cTable[i+1][j]) {
					cTable[i+1][j+1]=cTable[i][j+1];
					bTable[i][j]=1;
				}else {
					cTable[i+1][j+1]=cTable[i+1][j];
					bTable[i][j]=3;
				}
				
			}
			
		}
		System.out.print("最大子数组为:");
		printLCS(xArray, bTable, m-1,n-1);
		return cTable[m][n];
	}
	/*输出最佳路径即最长公共子序列*/
	public static void printLCS (char[] xArray,int[][] bTable,int i,int j) {
		if (i==-1||j==-1) {
			return;
		}
		if (bTable[i][j]==2) {
			printLCS(xArray, bTable, i-1, j-1);
			System.out.print(xArray[i]);
		}else if (bTable[i][j]==1) {
			printLCS(xArray, bTable, i-1, j);
		}else {
			printLCS(xArray, bTable, i, j-1);
		}
	}

}

*****************************************

控制台输出:

最大子数组为:BCBACBACB

长度为:9

本文转载自:http://blog.csdn.net/weitao1234/article/details/39181205

猪刚烈

猪刚烈

粉丝 22
博文 708
码字总数 110
作品 1
海淀
程序员
私信 提问
腾讯 2017 暑假实习生编程题(一):给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。

题目 回文串的特点是,逆序输出和正序输出是一样的。 所以这道题可以转化为:如果将此字符串逆序输出,那么两个字符串的最长公共子序列将是最长的回文字符串,那么剩余的值将是要删除的字符个...

TinyDolphin
2017/11/22
0
0
动态规划法(十)最长公共子序列(LCS)问题

问题介绍   给定一个序列X=X=,另一个序列Z=Z=满足如下条件时称为X的子序列:存在一个严格递增的X的下标序列,对所有的j=1,2,...,kj=1,2,...,k满足xij=zj.xij=zj.   给定两个序列XX和YY,...

jclian91
2018/06/12
0
0
删除部分字符使其变成回文串问题——最长公共子序列LCS问题

先要搞明白:最长公共子串和最长公共子序列的区别。 最长公共子串(Longest Common Substirng):连续 最长公共子序列(Longest Common Subsequence,LCS):不必连续 题目:给定一个字符串s...

牧师-Panda
2016/09/10
746
0
使用动态规划 实现字符级Diff & Patch

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

lqt0223
2018/02/13
0
0
触类旁通,经典面试题最长公共子序列应该这么答

原文链接:https://aiprocon.csdn.net/m/topic/ai_procon/index 输出: 3解释: 最长公共子序列是 "ace",它的长度是 3 ... else:...

AI科技大本营
08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Python 周刊第 418 期

新闻 PyCon US 2020 开始接受财务赞助! https://pycon.blogspot.com/2019/10/financial-aid-launches-for-pycon-us-2020.html2020年 Python 美国开发者大会,tips: 中国也有,可以赞助国内的...

iCodeBugs
3分钟前
0
0
ThreadLocal源码阅读

首先,从set方法入手, // ThreadLocalpublic void set(T value) { Thread t = Thread.currentThread(); ThreadLocalMap map = getMap(t);//这里可以看出,从Threa......

小海bug
12分钟前
1
0
成长之路 万事知行合一

思想决定行为,行为决定习惯,习惯决定性格,性格决定命运。 很多道理,不管是前辈给你指点说的也好,还是你自己看一些书籍学到的也好,如果不能够做到,就连那些不知道这个道理的人都不如。...

T型人才追梦者
15分钟前
1
0
uml图六种箭头的含义

在看一些技术博客的时候,经常会见到博客里画上很多uml图。因为经常会被这几种表达关系的箭头搞混,这里我就把常见的6种箭头表达的含义理一下。 泛化 概念:泛化是一种一般与特殊、一般与具体...

1只特立独行的猪
22分钟前
1
0
【在 Nervos CKB 上做开发】Nervos CKB 脚本编程简介[3]:自定义代币

原文作者:Xuejie 原文链接:https://xuejie.space/2019_09_06_introduction_to_ckb_script_programming_udt/ Nervos CKB 脚本编程简介[3]:自定义代币 CKB 的 Cell 模型和 VM 支持许多新的用...

NervosCommunity
56分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部