精华内容
下载资源
问答
  • 最长公共子序列问题,给定序列X=<x1,x2,…,xm>,Y=<y1,y2,…,yj>,就X和Y的最长公共子序列。 设X和Z是两个序列,其中X=<x1,x2,…,xm>,Z=<z1,z2,…,zk>,如果存在X的元素构成的按下标严格...
    1. 问题
      最长公共子序列问题,给定序列X=<x1,x2,…,xm>,Y=<y1,y2,…,yj>,就X和Y的最长公共子序列。
      设X和Z是两个序列,其中X=<x1,x2,…,xm>,Z=<z1,z2,…,zk>,如果存在X的元素构成的按下标严格排序递增序列<xi1,xi2,…,xik>,使得xij=zj,j=1,2,…,k,那么Z是X的子序列,Z含有的元素个数,称为子序列的长度。
      定义:设X和Y是两个序列,如果Z既是X的子序列,也是Y的子序列,则称Z是X和Y的公共子序列。

    背包问题

    1. 解析
      Xi=<x1,x2,…,xi>
      Yj=<y1,y2,…,yj>
      Zk=<z1,z2,…,zk>
      如果Zk是Xi和Yj的最长公共子序列,
      (1)xi = yj,那么zk = xi = yj,Zk-1是Xi-1和Yj-1的最长公共子序列
      (2)xi ≠ yj,那么zk ≠ xi,Zk-1是Xi-1和Yj的最长公共子序列
      (3)xi ≠ yj,那么zk ≠ yi,Zk-1是Xi和Yj-1的最长公共子序列

    实例:
    X=<A,B,C,D,C>
    Y=<B,D,C,B>
    m=1-5
    n=1-4

    (1)i=1
    a) j=1 X.A<>Y.B,C[1,1]=max{C[1,0],C[0,1]}=0,删除y
    b) j=2 X.A<>Y.D,C[1,2]=max{C[1,1],C[0,2]}=0,删除y
    c) j=3 X.A<>Y.C,C[1,3]=max{C[1,2],C[0,3]}=0,删除y
    d) j=4 X.A<>Y.B,C[1,4]=max{C[1,3],C[0,4]}=0,删除y
    (2)i=2
    a) j=1 X.B等于Y.B,C[2,1]=C[1,1]+1=1,删除两个
    b) j=2 X.B<>Y.D,C[2,2]=max{C[2,1],C[1,2]}=1,删除y
    c) j=3 X.B<>Y.C,C[2,3]=max{C[2,2],C[1,3]}=1,删除y
    d) j=4 X.B=Y.B,C[2,4]=C[1,3]+1=1,删除两个
    (3)i=3
    a) j=1 X.C<>Y.B,C[3,1]=max{C[3,0],C[2,1]}=1,删除x
    b) j=2 X.C<>Y.D,C[3,2]=max{C[3,1],C[2,2]}=1,删除y
    c) j=3 X.C等于Y.C,C[3,3]=C[2,2]+1=2,删除两个
    d) j=4 X.C<>Y.B,C[3,4]=max{C[3,3],C[2,4]}=2,删除y
    (4)i=4
    a) j=1 X.D<>Y.B,C[4,1]=max{C[4,0],C[3,1]}=1,删除x
    b) j=2 X.D=Y.D,C[4,2]=C[3,1]+1=2,删除两个
    c) j=3 X.D<>Y.C,C[4,3]=max{C[4,2],C[3,3]}=2,删除y
    d) j=4 X.D<>Y.B,C[4,4]=max{C[4,3],C[3,4]}=2,删除y
    (5)i=5
    a) j=1 X.C<>Y.B,C[5,1]=max{C[5,0],C[4,1]}=1,删除x
    b) j=2 X.C<>Y.D,C[5,2]=max{C[5,1],C[4,2]}=1,删除x
    c) j=3 X.C==Y.C,C[5,3]=C[4,2]+1=3,删除两个
    d) j=4 X.C<>Y.B,C[5,4]=max{C[5,3],C[4,4]}=3,删除y

    (1)X=5,Y=4
    查表(5,4) “3;删除y”
    X=<A,B,C,D,C>
    Y=<B,D,C,B>
    =>
    X=<A,B,C,D,C>
    Y=<B,D,C>
    (2)X=5,Y=3
    查表(5,3) “3;删除两个”
    X=<A,B,C,D,C>
    Y=<B,D,C>
    =>
    X=<A,B,C,D>
    Y=<B,D>
    输出C
    (3)X=4,Y=2
    查表(4,2) “2;删除两个”
    X=<A,B,C,D>
    Y=<B,D>
    =>
    X=<A,B,C>
    Y=< B >
    输出D
    (4)X=3,Y=1
    查表(3,1) “1;x”
    X=<A,B,C>
    Y=< B >
    =>
    X=<A,B>
    Y=< B >
    (5)X=2,Y=1
    查表(2,1) “1;删除两个”
    X=<A,B>
    Y=< B >
    =>
    X=< A >
    Y=<>
    输出B
    (6)X=1,Y=0
    最终输出<B,D,C>

    1. 设计
      在这里插入图片描述

    2. 分析
      LCS时间复杂度O(mn)

    3. 源码

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    //算法2:f(B, i, j)输出最长子串
    void LCS(vector< vector<int> > &B, string X, int X_len, int Y_len) {
        if (X_len == 0 || Y_len == 0) {
            return;
        }
        if (B[X_len][Y_len] == 3) {
            LCS(B, X, X_len - 1, Y_len - 1);
            cout << X[X_len - 1];
        }
        else if (B[X_len][Y_len] == 2) {
            LCS(B, X, X_len - 1, Y_len);
        }
        else if (B[X_len][Y_len] == 1) {
            LCS(B, X, X_len, Y_len - 1);
        }
    }
    int main()
    {
        string X = "ABCDC";
        string Y = "BDCB";
        int m = X.size();
        int n = Y.size();
        cout << "X: " << X << endl;
        cout << "Y: " << Y << endl;
        vector< vector<int> > C(m + 1, vector<int>(n + 1));
        vector< vector<int> > B(m + 1, vector<int>(n + 1));//1:删除y;2:删除x;3:删除两个
        //算法1:给出最长子串长度
        //初始化
        for (int i = 0; i <= m; i++)
        {
            C[i][0] = 0;
        }
        for (int i = 0; i <= n; i++)
        {
            C[0][i] = 0;
        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (X[i - 1] == Y[j - 1]) {
                    C[i][j] = C[i - 1][j - 1] + 1;
                    B[i][j] = 3;//删除两个
                }
                else {
                    if (C[i][j - 1] >= C[i - 1][j]) {
                        C[i][j] = C[i][j - 1];
                        B[i][j] = 1;//删除y
                    }
                    else {
                        C[i][j] = C[i - 1][j];
                        B[i][j] = 2;//删除x
                    }
                }
            }
        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                cout << C[i][j] << " ";
            }
            cout << endl;
        }
        cout << "最长公共子序列长度为:" << C[m][n] << endl;
        LCS(B, X, m, n);
        cout << endl;
    }
    
    
    
    展开全文
  • 求X和Yd最长公共子序列; 解析 Xi=< x1,x2,…,xi> Yj=< y1,y2,…,yj> Zk=< z1,z2,…,zk> 如果Zk是Xi和Yi的最长公共子序列 伪代码 源码 #include <stdio.h> #incl...

    问题

    给定序列 X=< x1,x2,…,xm> , Y=<y1,y2,…,yn>
    求X和Yd最长公共子序列;

    解析

    Xi=< x1,x2,…,xi>
    Yj=< y1,y2,…,yj>
    Zk=< z1,z2,…,zk>
    如果Zk是Xi和Yi的最长公共子序列
    在这里插入图片描述
    在这里插入图片描述

    伪代码

    在这里插入图片描述

    源码

    #include <stdio.h>
    #include <string.h>
    
    
    #define MAXLEN 30
    
    void LCS(char *x, char *y, int m, int n, int a[][MAXLEN], int b[][MAXLEN]) {
    	int i, j;
    	for (i = 0; i <= m; i++)	a[i][0] = 0;
    	for (j = 1; j <= n; j++)	b[0][j] = 0;
    	for (i = 1; i <= m; i++) {
    		for (j = 1; j <= n; j++) {
    			if (x[i - 1] == y[j - 1]) {
    				a[i][j] = a[i - 1][j - 1] + 1;
    				b[i][j] = 1;
    			}
    			else if (a[i - 1][j] >= a[i][j - 1]) {
    				a[i][j] = a[i - 1][j];
    				b[i][j] = 3;
    			}
    			else {
    				a[i][j] = a[i][j - 1];
    				b[i][j] = 2;
    			}
    
    		}
    	}
    }
    
    void PrintLCS(int b[][MAXLEN], char *x, int i, int j) {
    	if (i == 0 || j == 0)	return;
    	if (b[i][j] == 1) {
    		PrintLCS(b, x, i - 1, j - 1);
    		printf("%c", x[i - 1]);
    	}
    	else if (b[i][j] == 3)
    		PrintLCS(b, x, i - 1, j);
    	else
    		PrintLCS(b, x, i, j - 1);
    }
    
    int main() {
    	char x[MAXLEN] = { "AACDASDABDC" };
    	char y[MAXLEN] = { "ACFSADDA" };
    	int a[MAXLEN][MAXLEN],
    		b[MAXLEN][MAXLEN];
    	int m, n;
    	m = strlen(x);
    	n = strlen(y);
    
    	LCS(x, y, m, n, a, b);
    	PrintLCS(b, x, m, n);
    
    	return 0;
    }
    
    

    运行结果

    在这里插入图片描述

    复杂度

    O(mn)

    展开全文
  • 题目思想大概是这样:cabbeaf:回文子序列有:c,a,aa,bb,,aba,abba,e,f,最长的就是abba,所以输出长度为4 #include ...int main(){//思路就是求这个原字符串和它反转字符串的最长公共子序列 string str; cin

    题目思想大概是这样:cabbeaf:回文子序列有:c,a,aa,bb,,aba,abba,e,f,最长的就是abba,所以输出长度为4

    状态转移关系如下:


    #include <iostream>
    #include <algorithm>
    #include <string>
    int dp[1000][1000];
    using namespace std;
    int main(){//思路就是求这个原字符串和它反转字符串的最长公共子序列
    
      string str;
      cin>>str;
      string a=str;
      reverse(a.begin(),a.end());
      int len=str.length();
      for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
          if(str[i-1]==a[j-1]){
            dp[i][j]=dp[i-1][j-1]+1;
          }
          else{
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
          }
        }
      }
        cout<<dp[len][len];
      return 0;
    }


    展开全文
  • 小学期学的算法和做OJ题的各种经验总结最长公共子序列 LCS:最长上升子序列 LISDP: O(n^2^)代码贪心+二分O(nlogn)代码: 最长公共子序列 LCS: 正着遍历,倒着构造 c[i,j]表示:(x1,x2....xi) 和 (y1,y2...yj) 的...

    小学期学的算法和做OJ题的各种经验总结


    最长公共子序列 LCS:

    正着遍历,倒着构造
    最长子序列
    c[i,j]表示:(x1,x2....xi) 和 (y1,y2...yj) 的最长公共子序列的长度
    序列回溯,可以用栈。

    //dp初始化为0
    for(i=1;i<=lena;i++){
    	for(j=1;j<=lenb;j++){
    		if(a[i-1]==b[j-1]){
    			dp[i][j]=dp[i-1][j-1]+1;
    		}else{
    			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    		}
    	}
    }
    printf("%d\n",dp[lena][lenb]);
    

    最长上升子序列 LIS

    参考:https://blog.csdn.net/lxt_Lucia/article/details/81206439

    DP: O(n2)

    状态设计:F[i] 代表以 A[i] 结尾的 LIS 的长度

    边界处理:F [ i ] = 1 (1 <= i <= n)

    状态转移:遍历i之前的数中找到所有比A[i] 小的数的位置j,如果没有就是自身
    Fi={max(Fj+1),j=1i1Aj&lt;AiFi1,max(Fj+1)=1F_i = \begin{cases} \max(F_j + 1 ), &amp; j = 1\cdots i - 1且A_j &lt; A_i \\ F_i(初始化时为1),&amp; 第一个式子没有满足的条件,\\&amp;即\max(F_j+1)=1,则自己为序列开头 \end {cases}
    综合起来就变成了
    Fi=max{Fj+1, Fi  where 1ji1 and Aj&lt;Ai}F_i = \max\{F_j+1,\space F_i \ | \ where\ 1\le j \le i-1 \ and \ A_j \lt A_i\}
    ans即为以每个数为结尾的最长子序列中最大的

    代码

    for (int i = 1; i <= n; i++) f[i] = 1;
    	
    for (int i = 1; i <= n; i++) 
    	for (int j = 1; j < i; j++)
    		if (a[j] < a[i])
    			f[i] = max(f[i], f[j] + 1);
    
    for (int i = 1; i <= n; i++)
    	ans = max(ans, f[i]);
    

    贪心+二分O(nlogn)

    low 数组,lowm 表示长度为m的LIS结尾元素的最小值(初始化为INF),对于每一个长度为m的LIS,一定是结尾元素越小越有潜力拼的更长。因此我们维护low数组,用len记录LIS当前的长度,对于每一个ai

    • 如果ai > lowlen 就拼到LIS里,即令low++len=ai
    • 如果ai < lowm(m是满足条件 lowk > ai 的第一个位置) ,说明ai作为长度为m的LIS的结尾元素更有潜力,就把ai 跟lowm替换。
    • 找满足条件的第一个位置可以利用二分搜索,
    • 可以直接用STL函数lower_bound(默认小于比较)
      • 用法:lower_bound(first, last, k[, cmp]) 返回first到last中不满足*it<k或cmp(*it,k)的第一个位置(地址),默认情况下即返回数组中第一个大于k的数的地址;
      • int m = lower_bound(low+1, low+1+len, a[i]) - low;地址 - 地址 = 下标

    代码:

    int main() {
    	int low[MAXN] = INF;//长度为m的LIS结尾元素的最小值
    	int a[MAXN], n;
    	//初始条件
    	low[1] = a[i];
    	int len=1;
    
    	for (int i = 2; i <= n; i++){
    		if(a[i]>low[len]) low[++len]=a[i];//拼入LIS
    		else{
    			//找到第一个大于a[i]的位置,更新成a[i]
    			int m = lower_bound(low+1,low+1+n,a[i]) - low;
    			low[m] = a[i];
    		}
    	}
    	cout<<len;
    
    	return 0;
    }
    
    展开全文
  • 【每日算法最长公共子序列题目基本概念算法思路图解计算LCS初始化 题目 两个数组的,两个数组中都包含的最长序列 最长公共子序列,全称Longest Common Subsequence,简称LCS 基本概念 这里需要了解一下子序列...
  • 最长公共子序列 LeetCode 1143. 最长公共子序列 给定两个字符串text1和text2,返回这两个字符串的最长公共子序列。 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除...
  • 最长公共子序列LCS

    2018-04-10 17:13:37
    最长公共子序列LCS 一些基本概念以及LCS算法核心思想摘录自别人的博客,在此申明。(没必要做不必要的重复劳动,这篇博客和我看的一本书中的内容很相似,后面的代码改编自原书中的实现,书中) 1. LCS相关基本...
  • 动态规划算法典型应用之最长公共子序列LCS问题 继续学习动态规划233。之前有了投资问题和背包问题的基础,LCS问题比较好理解了。先来看看LCS的定义。 算了,也不整定义了,不太好理解,直接上例子。 有一个X...
  • 算法 最长公共子序列 子序列的定义: 如果Z是A的子序列,则A中包含Z的所有排列元素,且这些元素在各自排列中的顺序是一致的 例如Z={BCA},A={ABCBDAB} 最优子结构 设C是LCS的长度 则 if(i==0||j==0) C[i,j]=...
  • 注:这里的子序列和之前数组所说的子序列不太一样,这里的子...注:我们这里讨论的是最长公共子序列,即可以不连续 1、暴力法。穷举。时间复杂度2m+n 转载于:https://www.cnblogs.com/minconding/p/10454295.html...
  • 三 动态规划算法最长公共子序列LCS问题 2011 12 13重写
  • 最长公共子序列(LCS)算法实验 最长公共子序列(LCS)算法实验 最长公共子序列(LCS)算法实验
  • 简介: 一个给定序列的子...最长公共子序列(Longest Common Subsequence,LCS)是长度最长的子序列。 算法思想: 使用动态规划求解,引入二维数组dp,dp[i][j]存储的是序列Xi(x1,x2,…xi)和Yj(y1,y2,…yi)的最长公...
  • 给定两个字符串,求最长公共子序列及其长度(不同于最长公共子串的是公共子串要求连续) 思路: 设字串为a,b 建立二维数组c用于打表,建立二维数组d,用于记录路径,其中c[i][j]表示的是a的前i个字符构成的字串和b...
  • 实现了求最长公共子序列算法,内容简单易懂,代码也很短
  • 最长公共子序列LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个...
  • LCS算法的精髓就是动态规划,序列其实不仅限于字符序列,因此我用模版类对该算法进行了封装,里面提供了尽量方便的函数来进行该算法的使用,该实现并不追求速度最快化,而是尽量让该算法类能支持重用,若发现算法有...
  • 1006 最长公共子序列Lcs LCS算法经常被应用到生物学上,去比对两个DNA的差别,我们使用动态规划的方法来解决该问题。 用 dp[i,j] 表示字符串A的前 i 个字符与字符串B的前 j 个字符做匹配,得到的LCS的长度。 模板...
  • 1.问题 定义 设 X 和 Z 是两个序列,其中 X = <x1,x2….,xm> Z = <z1,z2,….,zk> 如果存在X的元素构成的按...设X和Y是两个序列,如果Z既是X的子序列,也是Y的子序列,则称Z是X和Y的公共子序列 实例: X =
  • 最长公共子序列问题——LCS算法 问题描述: 给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。比如两个串为: abcicba abdkscab ab是两个串的子序列,abc也是,abca也是,其中abca是这两个字符...
  • 很多人在上学的时候都有过对毕业论文进行查重的经历,一般可以通过CNKI,知网等平台提交自己的论文,平台将论文与其他论文进行匹配查重,最终得到一个相似度。...最长公共子序列,英文名称为Longest Commo...
  • 首先确定什么是最长公共子序列: 最长公共子串(longest common substring) :其中的子串是原串的一个连续的部分; 最长公共子序列(longest common subsequence):是不改变序列的顺序,从序列中得到任意的元素...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,085
精华内容 434
热门标签
关键字:

最长公共子序列lcs算法