精华内容
下载资源
问答
  • 求最长公共子序列

    2016-06-24 16:21:43
    求最长公共子序列

    求最长公共子序列


    Description

    字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。
    令给定的字符序列 X=x0x1xm1,序列 Y=y0y1yk1X 的子序列,存在 X 的一个严格递增下标序列 <i0i1ik1>,使得对所有的 j=01k1,有 xij=yj
    例如,X=ABCBDABY=BCDBX 的一个子序列。
    对给定的两个字符序列,求出他们最长的公共子序列。


    Input

    1 行为第 1 个字符序列,都是大写字母组成,以”.”结束。长度小于 5000
    2 行为第 2 个字符序列,都是大写字母组成,以”.”结束,长度小于 5000


    Output

    输出上述两个最长公共子序列的长度。


    Sample Input

    ABCBDAB.
    BACBBD.


    Sample Output

    4


    Solution

    fi,j 表示 xi 个字符与 yj 个字符的最长公共子序列的长度,则
    xi1=yj1

    fi,j=fi1,j1+1

    xi1yj1
    fi,j=MAX{fi1,j,fi,j1}

    Code

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    #define Max(x,y) ((x)>(y)?(x):(y))
    
    using namespace std;
    
    char s1[5010],s2[5010];
    int f[5010][5010];
    
    int main(){
    
        freopen("lcs.in","r",stdin);
        freopen("lcs.out","w",stdout);
    
        scanf("%s%s",s1,s2);
    
        int l1=strlen(s1)-1,l2=strlen(s2)-1;
    
        for(int i=0;i<l1;i++)
            for(int j=0;j<l2;j++)
                if(s1[i]==s2[j])
                    f[i+1][j+1]=f[i][j]+1;
                else
                    f[i+1][j+1]=Max(f[i+1][j],f[i][j+1]);
        printf("%d\n",f[l1][l2]);
        return 0;
    }
    展开全文
  • 求最长公共子序列,c语言编程。求最长公共子序列,c语言编程。求最长公共子序列,c语言编程。求最长公共子序列,c语言编程。求最长公共子序列,c语言编程。
  • 求最长公共子序列长度

    千次阅读 2019-03-15 21:06:37
    求最长公共子序列(子序列可以不连续)2.最长连续子串 1.求最长公共子序列(子序列可以不连续) 这是一道动态规划题,设二维数组dp[i][j],dp[i][j]表示a串前i个字符(包括第i个)与b串前j个字符(包括第j个)所有的...

    求两个字符串的公共子序列


    1.求最长公共子序列(子序列可以不连续)

    这是一道动态规划题,设二维数组dp[i][j],dp[i][j]表示a串前i个字符(包括第i个)与b串前j个字符(包括第j个)所有的公共子序列的最长长度。
    例如,a串abbcd,b串abcd,dp[3][3]就表示的a的前三个字符与b的前三个字符的最长公共子序列长度,值为2。a串中的ab与b串中的ab一致,长度为2。
    求dp数组的方法为:
    dp[i][j] = 0 , i == 0 || j == 0
    dp[i][j] = dp[i-1][j-1] +1 , a[i] = b[j]
    dp[i][j] = max(dp[i-1][j],dp[i][j-1]) , a[i] !=b[j]

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int main(){
        string a,b;
        cin>>a>>b;
        int alen = a.size();
        int blen = b.size();
        int dp[100][100];
        for(int i=0;i<alen+1;i++) dp[i][0]=0;   //若i==0或j==0
        for(int j=0;j<alen+1;j++) dp[0][j]=0;  //dp[i][j] = 0
        for(int i=1;i<alen+1;i++){
            for(int j=1;j<blen+1;j++){
                if(a[i-1]==b[j-1]){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else{
                	dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                }
                cout<<dp[i][j]<<"  ";   //输出当前dp矩阵
            }
        }
        cout<< dp[alem][blen];       //dp[alem][blen]即为当前两个串的最长公共子序列长度
    }
    
    

    2.最长连续子串

    求最长连续子串比不连续的简单了一些,只需删除上边代码里的else部分即可,这里的dp[i][j]可以理解为以a的第i个字符与b的第j个字符为结尾的最长公共子串的长度,由此可得a[i] != b[j]时,dp[i][j] = 0

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int main(){
        string a,b;
        cin>>a>>b;
        int alen = a.size();
        int blen = b.size();
        int dp[100][100];
        int Max=0;
        for(int i=0;i<alen+1;i++) dp[i][0]=0;
        for(int j=0;j<alen+1;j++) dp[0][j]=0;
        for(int i=1;i<alen+1;i++){
            for(int j=1;j<blen+1;j++){
                if(a[i-1]==b[j-1]){
                    dp[i][j] = dp[i-1][j-1] +1;
                }
                cout<<dp[i][j]<<"  ";
                if(dp[i][j]>Max)
                    Max = dp[i][j];     //保存数组里的最大值
            }
            cout<<endl;
        }
        cout<< Max;
    
    }
    
    
    展开全文
  • 题目:给定两个序列X={x1,x2,…xm},Y={y1,y2,…yn},找出X和Y的最长公共子序列。 分析: 1 最长公共子序列概念 实现明确一个点就是,子序列是一个序列中去掉若干元素后得到的序列,也就是说子序列的元素下标是递增...

    题目:
    给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},求X和Y的最长公共子序列。

    1 最长公共子序列概念

    实现明确一个点就是,子序列是一个序列中去掉若干元素后得到的序列,也就是说子序列的元素下标是递增的就行,不需要在原序列中连续。

    最长公共子序列,显而易见就是序列X和Y都有的最长的子序列。

    2 BruteForce 暴力求解法

    对于序列X的所有长度不超过Y的子序列,都检查是否也是Y的子序列,在检查过程中记录长度做长的。

    假设X长度小于Y,X有m个元素,每个元素都有2种选择,在或不在,所以X一共有2m个不同子序列。此方法需要指数时间。

    3 DP 动态规划法

    ① 最优子结构

    首先我们来检查下LCS问题能不能用DP来做。

    DP的问题,需要分成的子问题具有最优子结构性质(问题的最优解中包含着每个子问题的最优解),子问题高度重复性,(当然不用把这个理解成必须,只是说这样的问题比较适合用DP来做)。

    假设X和Y的最长公共子序列为Z={z1,z2,…,zk},
    则把LCS问题,分成下面这样的几个子问题:
    (1)若xm=yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列。
    (2)若xm≠yn,且zk≠xm,则Zk是Xm-1和Yn的最长公共子序列。
    (2)若xm≠yn,且zk≠yn,则Zk是Xm和Yn-1的最长公共子序列。

    现在来证明一下,以上的子问题具有最优子结构性质,用反证法,
    (1) 若zk不等于xm,因为xm=yn,所以把xm加在zk后面,{z1,z2,…,zk,xm}是X和Y的长度为k+1的公共子序列,这与Z是X和Y的最长公共子序列矛盾,因此,必有zk=xm=yn,Zk-1
      若Zk-1不是Xm-1和Yn-1的最长公共子序列,则Xm-1和Yn-1存在长度比k-1大的公共子序列,则将xm加在其后面,就产生了一个X和Y的长度比k大的公共子序列了,这与这与Zk是X和Y的最长公共子序列矛盾,
      综上两点,故zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列。

    (2)若Zk不是Xm-1和Yn的最长公共子序列,则Xm-1和Yn还存在更长的最长公共子序列W,则W也是X和Y的公共子序列,且W长度>k,这与Z(长度为k)是X和Y的最长公共子序列矛盾。故Zk是Xm-1和Yn的最长公共子序列。
    (3)若Zk不是Xm和Yn-1的最长公共子序列,则Xm和Yn-1还存在更长的最长公共子序列W,则W也是X和Y的公共子序列,且W长度>k,这与Z(长度为k)是X和Y的最长公共子序列矛盾。故Zk是Xm和Yn-1的最长公共子序列。
    综上三点,两个序列最长公共子序列包含了这两个序列的前缀的最长公共子序列,(这句话有点拗口,其实就是X和Y的LCS包含了X1≤r≤m和Y1≤s≤n的LCS)因此最长公共子序列具有最优子结构性质。

    ② 子问题的递归结构
    用C[i][j]记录序列Xi和Yj的LCS长度。

    在这里插入图片描述

    ③求最优值,输出LCS
    为了构造出LCS,引入一个二维数组b[m][n],用来记录c[i][j]的值是由哪个子问题得到的。
    (1)b[i][j]=1,则表示Xi和Yj的LCS是从Xi-1和Yj-1的LCS得到的,在Xi-1和Yj-1的LCS后加上一个xi得到。
    (2)b[i][j]=2,则表示Xi和Yj的LCS是从Xi-1和Yj的LCS得到的,就是Xi-1和Yj的LCS。
    (3)b[i][j]=3,则表示Xi和Yj的LCS是从Xi和Yj-1的LCS得到的,就是Xi和Yj-1的LCS。
    (4)b[i][j]=4,则表示Xi和Yj的LCS是从Xi-1和Yj的LCS,和Xi和Yj-1的LCS得到的,此时情况表示的是,C[i-1,j]=C[i,j-1]的情况,这时候有两个元素可能不同的,但是长度相同的LCS,为了不遗漏,所以要两个方向进行搜索。

    注意,一般资料上都是分成(1),(2),(3)这三种情况,将(4)并入(2)中,这样会导致算法不能搜索到所有的LCS,(当然最长长度可以正确得出,只是LCS往往不止一个,得不到所有的LCS情况),但是加上(4)后,会导致重复输出的问题,比如BA和BC会输出两个B。但是如果没有(4),如BED和BDE会只输出BE或者BD。
    -----(结合代码看更容易理解)----

    4 java代码实现
    注意几个点:
    (1)数组C的大小应该是[X.length+1][Y.length+1],要存储子序列长度为0的情况。C[1][2]表示,X的第一个元素和Y的前两个元素的LCS长度,C[i][0]和C[0][j]都是0,注意下碰到X和Y不要数组越界了。
    (2)增加了状态(4)后,会导致出现分支:

    private static void printLCS(char[]X,char[]Y,int i,int j,int[][]b)
    {
    	if(i==0||j==0) return;//递归出口
        if(b[i][j]==1)
    			{
    		          printLCS(X,Y,i-1,j-1,b);
    		          System.out.print(X[i-1]);//因为是递归,故X[i-1]输出的时候正好是它本来在的位置,不会逆序	 
    			}
    	else if(b[i][j]==2)
    		printLCS(X,Y,i-1,j,b);
    	else if(b[i][j]==3)
    		printLCS(X,Y,i,j-1,b);
    	else 
    		{
    		   printLCS(X,Y,i,j-1,b);
    		   System.out.print('/');
    		   printLCS(X,Y,i-1,j,b);
    		}
    	
    }
    

    但是这样输出在某些情况下不会输出正确的结果,如ABCBDAB和BDCABA会输出:BD/BCAB/BCBA,而正确输出应该是BDAB/BCAB/BCBA,看下递归过程:
    在这里插入图片描述
    也就说递归时候先到第一个分支b(4,3)输出了BC,接着到另一个分支b(5,2)输出了BD,最后再return一起输出AB,所以导致了输出BDAB/BCAB,变成了BD/BCAB。
    解决方法:
    不能利用递归的特点输出序列了,只能用一个字符串把结果都保存下来,最后逆序输出。(如果不要求输出全部的LCS,可以按上述方法做,并且不用加b[][]的第四个状态)
    输出修改如下:

    private static void printLCS(char[]X,char[]Y,int i,int j,int[][]b,String s)
    {
    	if(i==0||j==0) //递归出口
    	{
            StringBuilder s2=new StringBuilder(s);
            System.out.println(s2.reverse());
            return;
    	}
        if(b[i][j]==1)
    			{
                       s=s+X[i-1];
    		          printLCS(X,Y,i-1,j-1,b,s);
    			}
    	else if(b[i][j]==2)
    		printLCS(X,Y,i-1,j,b,s);
    	else if(b[i][j]==3)
    		printLCS(X,Y,i,j-1,b,s);
    	else 
    		{
    		   printLCS(X,Y,i,j-1,b,s);
    		   printLCS(X,Y,i-1,j,b,s);
    		}
    }
    

    这里有个很巧妙的一点就是,用String作为参数,String作为参数传值,是不会改变String本身的值的,虽然String是引用数据类型,但是String是不可变的,再利用StringBuilder的倒置函数,可以直接输出结果。如果你把StringBuilder作为参数,StringBuilder的对象是能修改的,比如说BDAB和BCAB,从AB开始产生分支,第一个分支得到BDAB,但是s也被修改成了BDAB,这时候再进行第二个分支,就会输出BCBDAB了。当然如果是C++,直接传就行,没有都是传引用的烦恼。

    整体代码如下:
    源代码

    5 算法优化
    其实这个算法里,可以不用b[][]数组,输出时候,可以直接用C[][]数组自身进行比较,来确定C[][]的值是由哪个值所确定的。不想写了,网上找了个实现:代码
    可以参考一下。

    展开全文
  • 求最长公共子序列,Java实现,详细分析!

    一、题目说明:

    有字符序列A=xyzzyxzyxxyx,B=zyxxyyzyxyzy,求A、B的最长公共子序列。(输出最优值与最优解)

     

    二、思路说明:

    算法的核心思想有点类似于合并两个有序的子序列;使用一个“指针”从子序列1起点开始,用于指代其中的元素,使用另一个“指针”从子序列2的起点开始,用于指代其中的元素;然后比较其大小,插入到新的序列中。

    但该算法不同的地方在于:利用数组的下标替代了上面“指针”,然后也不是比较大小,而是比较是否相等。因为两组序列中的任何两个元素可能发生比较,所以利用二维数组表示所有的比较可能。

    在元素进行具体比较的时候,元素相等时,两个序列待处理的元素都减少一个,当元素不相等的时候,就有两种选择了,帮助我们抉择的点就是哪条“路”已产生的公共元素更多。

    这就进一步要求我们在具体求解的过程中,既需要知道前面已经求解的公共元素个数,还需知道已经走过的求解路径。因此我们在整个求解过程中借助了两个二维数组,一个用来积累你的局部最优解,一个用不同的数字来表示你的求解路径。

    在最终提取结果的时候,就可以借助第二个二维数组元素的取值反向回溯其最优解的求解路径,并根据相应元素下标的取值知晓是对于哪个公共元素。

     

    三、代码求解:

    import java.util.Scanner;
    
    public class demo {
    	public static void main(String[] args) {
    		//输入阶段
    		System.out.println("请输入第一个字符串:");
    		Scanner s = new Scanner(System.in);
    		String strx = s.next();
    		System.out.println("请输入第二个字符串:");
    		String stry = s.next();
    		
    		//初始化(注意下标的问题,因为后续程序(指代第40行)的原因,需要多留出空位,保持下标数字同步!)
    		//个人的考虑,我觉得这样好处理,有别的想法的小伙伴可以在下标的处理上可以自己构建,保持同步就好了!
    		int m = strx.length();
    		int n = stry.length();
    		//因为Java语言本身的特性,所以数组c和b自动初始化了
    		int [][]c = new int[m+1][n+1];
    		//用于存储最长公共子序列的长度及中间过程
    		int [][]b = new int[m+1][n+1];
    		//用于后续输出最长公共子序列,记录着求解路径
    		char[]x = new char[m+1];
    		for(int i=1;i<=m;i++)//真实的数据是从下标1开始存储的
    			x[i] = strx.charAt(i-1);
    		char[]y = new char[n+1];
    		for(int j=1;j<=n;j++)
    			y[j] = stry.charAt(j-1);
    		//调用函数进行求解初始化数组b和c
    		maxLength(m, n, x, y, c, b);
    		//于数组b中获得其求解路径,在对应的数组x中对应输出
    		maxAnswer(m, n, x, b);
    		System.out.println();
    		System.out.println("最长公共子序列的长度为:"+count);
    		
    		
    	}
    	public static void maxLength(int m,int n,char[] x,char[] y,int[][]c,int[][]b) {
    		int i,j;		
    		for(i = 1;i<=m;i++) {
    			for(j = 1;j<=n;j++) {//i,j的取值意味着两个字符串比较元素的改变
    				//使用1、2、3区分其路径方位
    				//整体来说:c[i][j]的一步步取值将长度累计下去了,所以在数组c的右下角元素值即子序列最大长度
    				if(charEqual(x[i], y[j])) {//此时元素相等,子序列长度+1
    					c[i][j] = c[i-1][j-1]+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;//取左边的
    				}
    			}
    		}
    	}
    	
    	//用于比较字符元素是否相等
    	public static boolean charEqual(char a,char b) {
    		Character A = new Character(a);
    		Character B = new Character(b);
    		if(A.equals(B))
    			return true;
    		return false;
    	}
    	
    	public static int count = 0;//计数
    	//用于输出结果
    	public static void maxAnswer(int i,int j,char[] x,int[][]b) {	
    		if(i==0||j==0)
    			return;
    		
    		//相当于对求解过程思路的原路回溯求解
    		if(b[i][j]==1) {
    			maxAnswer(i-1, j-1, x, b);//右上角
    			count++;
    			System.out.print(" "+x[i]);
    		}else if(b[i][j]==2) {
    			maxAnswer(i-1, j, x, b);//上面
    		}else {
    			maxAnswer(i, j-1, x, b);//左边
    		}
    		
    	}
    }
    

     

    四、个人愚见(进一步优化):

    其实在数组c构建的过程中也蕴含了方位、路径等信息,所以对于数组b起到的功能是可以被取代的,只不过信息的提取处理略有不同罢了

    flag:等我闲下来就把后面不用数组b的代码整一下,现在暂时没时间(*^_^*)!

    待续... ...

    展开全文
  • 在文本比较算法中有许多的算法,如最小编辑距离,线性空间求最长公共子序列等。如果,我们需要出两个字符串的相似度或者是距离的时候可以采用最小编辑距离算法,有时候我们可能需要求出两个字符串不同的地方,...
  • 动态规划法求最长公共子序列问题 一、实验目的及要求: 实验目的:本实验主要清楚动态规划法的主要思想,如何利用动态规划算法解决实际问题,通过动态规划法求解最长公共子序列问题,利用测试数据对最长公共子序列...
  • 一、求最长公共子序列 1、问题描述: 从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下地字符按原来顺序组成的串。例如:“ ”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串...
  • 本文主要通过求解最长公共子序列介绍动态规划算法的思想,首先介绍动态规划法的概念,动态规划法解题的步骤,然后介绍什么是最长公共子序列,按照动态规划法的步骤计算两个序列的最长公共子序列。 最后通过举例求解...
  • 【洛谷】P1439 【模板题】求最长公共子序列 1.题意 给出两个序列,如何出其最长公共子序列? 2.分析 step1.映射序列 step2.用O(NlogN)最长不下降子序列
  • 求最长公共子序列 递推 void solve() { for (int i = 0; i ; ++i) { for (int j = 0; j ; ++j) { if (s1[i] == s2[j]) { dp[i + 1][j + 1] = dp[i][j] + 1;
  • Algorithm:C++/python语言实现之旋转数组最小值、零子数组、求最长公共子序列和最长公共子串、LCS与字符串编辑距离 目录 一、旋转数组最小值 1、分析问题 2、解决思路 二、零子数组 1、算法...
  • Java求最长公共子序列

    2019-03-25 16:23:11
    公共子序列不同于公共子串,如“hello”与“hleeo” 最大公共子序列为:heo (不要求连续) 最大公共子串为:h 对过程不好理解的,推荐看一下这个:远洋号 代码如下: public class Run { public static void main...
  • 求最长公共子序列LCS

    2016-11-22 22:43:16
    问题描述:给定两个序列,例如 X = “ABCBDAB”、Y = “BDCABA”,它们的最长公共子序列的长度。 下面是求解时的动态规划表,可以看出 X 和 Y 的最长公共子序列的长度为4: 输出一个最长公共子序列并不难...
  • 最长公共子串和最长公共子序列的区别: 最长公共子串和最长公共子序列的区别为:子串是串的一...题目:两个字符串中的最长公共子序列。 比如: string s1 = “ABCBDAB”; string s2 = “BDCABA”;它们的lcs是:BCB
  • 【基础算法】求最长公共子序列 时间限制: 1 Sec 内存限制: 64 MB 题目描述 一个给定序列的子序列是在该序列中删去若干元素(也可以不删去)后得到的序列。例如Z="BCDB" 就是X="ABCBDAB"的一个子序列,而Z=...
  • 求最长公共子序列(LCS)   思路: 经典的动态规划法, c[i,j]表示Xi与Yj的最长公共子序列, 其中 Xi = {x1,、、、xi} Yj = {y1,、、、yj} 注意:这里的子序列在原序列中可以是不连续的。
  • 583. 两个字符串的删除操作 给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。 示例: 输入: “sea”, “eat” ...求最长公共子序列 c...
  • string1和sring2的最长公共子序列; 如果采用递归算法存在大量重复,浪费资源空间,算法复杂度为指数; 故采用似拙实巧的递归算法,核心是添加了一组初始化为0的行列 如果能让c++填充这样一个二维数组,数组的...
  • 最长公共子序列(LCS) 定义:在序列X和序列Y中同时出现的元素,按照脚标从小到大排列的这样的序列。  String x = "ABCBDABGGGTT";  String y = "BDCABATGGGTT"; x,y的最长公共子序列为...
  • 程序分为两个部分LCSLength()函数寻找最长公共子序列,LCS()函数打印最长公共子序列 具体代码如下 #include<iostream> #include<iomanip> using namespace std; int main() { int c[7][7],b[7][7]; ...
  • #include <iostream> #include<algorithm> #include<vector> #include <string>...int lcs(string str1, string str2) //最长公共子序列 { int len1 = str1.size(); int...
  • 假设两个序列 A,B,找两者的最长公共子序列; 第一步: 我们要去找出 A中所有与 B 相同的元素,这些元素在 B中的位置,各自为一个集合;比如 A = { a c f d } ,B = { c f g c a } , 则有 (从 i = 1 ...
  • 动态规划:求最长公共子序列问题

    千次阅读 2017-01-07 17:59:19
    最长公共子序列问题: 子序列是指在原序列中删去若干元素(这些元素可以不相邻)后得到的序列。例如X=abcbdab,Y=bdcaba,bca和bcba都是X和Y的公共子序列,且后者是最长的公共子序列。给定两个序列X(m)={x[1],x[2],....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,819
精华内容 15,127
关键字:

求最长公共子序列