最长公共子序列 订阅
最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列。 [1]  最长公共子序列问题是一个经典的计算机科学问题,也是数据比较程序,比如Diff工具,和生物信息学应用的基础。它也被广泛地应用在版本控制,比如Git用来调和文件之间的改变。 展开全文
最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列。 [1]  最长公共子序列问题是一个经典的计算机科学问题,也是数据比较程序,比如Diff工具,和生物信息学应用的基础。它也被广泛地应用在版本控制,比如Git用来调和文件之间的改变。
信息
描    述
两段文字之间的“相似度”
建议算法
动态规划
简    称
LCS
应用学科
数据结构
分    别
是两个或多个已知序列的子序列
中文名
最长公共子序列
计    算
改动前后文字的最长公共子序列
应用领域
计算机科学和生物信息学等
外文名
The longest common subsequence
最长公共子序列定义
最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
收起全文
精华内容
下载资源
问答
  • 最长公共子序列(详细代码 注释 分析 以及求出最长公共子序列内容方法)
    2022-04-25 22:15:47

    最长公共子序列

    文章有些长,希望能够耐心看完,并且对你有帮助,文章是自己看了书之后,总结的,如果有什么错误的地方,欢迎指出。

    一些基本的概念:

    子序列: 原序列中删除若干个元素得到的序列,即原序列中可以不连续的一段

    子串: 原序列中任意个连续的序列元素组成的序列,即原序列中必须连续的一段。

    (两者的元素顺序必须和原序列中的顺序一样)

    最长公共子序列: 一个序列即是X序列的子序列,也是Y序列的子序列,则该序列称为为X和Y的公共子序列。对于两个序列的公共子序列是不唯一的,因此,最长公共子序列顾名思义就是长度最长的公共子序列。

    思路分析:

    方一、从最优子结构去考虑

    求最长公共子序列长度:

    分析:

    ​ 因为动态规划的题目是满足最优子结构(最优解包含其子问题的最优解)这一基本条件的,因此我们通过分析最优子结构的特征,从而推出最优值的递推式,然后从子问题最优解出发,求解出整个问题的最优解即可。

    ​ 假设一个最优子结构情况,对于一个序列Z = {z1, z2, …… , zk}是 X = {x1, x2, ……, xm} 和 Y ={y1, y2 , ……, yn}的最长公共子序列,根据对最后一个元素考虑,我们可以分成三种情况来具体讨论:

    1)xm = yn = zk

    ​ 将xm和yn的值作为序列Z的最长公共子序列的最后一个元素,如果去掉xm和yn,那么对于序列Z的最长公共子序列的长度肯定会减小1,即c[i - 1] [j - 1] = c[i] [j] - 1; 因此,当xm = yn时的递推公式是: c[i] [j] = c[i - 1] [j - 1] + 1;

    (为什么要将xm和yn值做为最长公共子序列最后一个元素?你想,两个序列相等的元素且都在最后一个,并且和已知最长公共子序列的最后一个元素相等,无论X和Y前面怎么取公共部分,是不是最后这两个元素都可以作为一个公共部分加入到公共子序列的末尾)

    2)xm ≠ yn, xm ≠ zk

    ​ 表明xm肯定不会作为最长公共子序列的最后一个元素,那么我们把xm去掉,对于{x1, x2,……, xm-1} 和 {y1, y2,……, yn -1}的最长公共子序列也还是{z1, z2,……, zk-1}

    3)xm ≠ yn, yn ≠ zk

    ​ 同理2)情况

    由1)2)3)得最优值的递推式:

    对于c[i] [j]数组:指只取X前i个元素和只取Y前j个元素能够得到的最长公共子序列的值(即存放最优子结构的值)。

    由1)可知,如果xi = yj,那么可以从没有xi和yj的最优子结构即c[i - 1] [j - 1]转移过来

    即 c[i] [j] = c[i - 1] [j - 1] + 1;

    由2)3)可知,如果xi ≠ yj, 那么我们只需要取xi和yj-1最优子结构和xi-1和yj最优子结构的最大长度即可。

    即c[i] [j] = max(c[i] [j - 1] , c[i - 1] [j] );

    综上可以得出递推式:

    请添加图片描述

    自底向上求出问题的最优解:

    ​ 对子结构考虑的最优情况,得出的递推式是对所有求子问题的最优解适用的,通过该递推公式,自底向上计算子问题的最优值,那么最后的答案也肯定是最优的(这也就是动态规划的最优子结构的特征)

    代码:

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 1010;
    char s1[N], s2[N];
    int len1, len2;
    int c[N][N];
    int main()
    {
        //最优子结构状态值初始化(当然也可以不写,因为全局变量默认为0)
        memset(c, 0, sizeof(c));
        //输入序列s1和s2的长度
        cin>>len1>>len2;
        //输入需要求最长公共子序列的序列s1和s2
        cin>>s1+1>>s2+1;  
        for(int i = 1; i <= len1; i ++){
            for(int j = 1; j <= len2; j ++){
                if(s1[i] == s2[j])c[i][j] = c[i - 1][j - 1] + 1;
                else c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
        cout<<c[len1][len2]<<'\n';
        return 0;
    }
    

    求最长公共子序列内容:

    分析:

    对于一个最优子结构c[i] [j]的来源一共有三个,分别是

    1)c[i] [j] = c[i - 1] [j - 1] + 1;

    2)c[i] [j] = c[i - 1] [j] ;

    3)c[i] [j] = c[i] [j - 1];

    在自底向上计算最优值的时候,我们可以开一个临时的数组b[i] [j]去记录这3个来源,然后根据最值反向追踪最长公共子序列:

    1)b[i] [j] = 1, 即表示取了x[i]或y[j]作为最长公共子序列的一部分,我们输出即可。

    2)b[i] [j] = 2,即表示当前c[i] [j]的状态来自c[i - 1] [j],我们追踪c[i - 1] [j]

    3)b[i] [j] = 3, 即表示当前c[i] [j]的状态来自c[i] [j - 1],我们追踪c[i] [j - 1]

    代码:

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 1010;
    char s1[N], s2[N];
    int len1, len2;
    int c[N][N];
    int b[N][N];
    void print(int i, int j){
        if(i == 0 || j == 0)return;
        if(b[i][j] == 1){
            print(i - 1, j - 1);
            cout<<s1[i];
        }
        else if(b[i][j] == 2)print(i - 1, j);
        else print(i, j - 1);
    }
    int main()
    {
        //最优子结构状态值初始化
        memset(c, 0, sizeof(c));
        //输入序列s1和s2的长度
        cin>>len1>>len2;
        //输入需要求最长公共子序列的序列s1和s2
        cin>>s1+1>>s2+1;  
        for(int i = 1; i <= len1; i ++){
            for(int j = 1; j <= len2; j ++){
                if(s1[i] == s2[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;
                }
            }
        }
        print(len1, len2);
        // cout<<c[len1][len2]<<'\n';
        return 0;
    }
    

    当然如果你不想浪费空间,你也可以不用这个临时数组b,直接通过c数组判断即可:

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 1010;
    char s1[N], s2[N];
    int len1, len2;
    int c[N][N];
    void print(int i, int j){
        if(i == 0 || j == 0)return;
        if(c[i][j] == c[i - 1][j - 1] + 1){
            print(i - 1, j - 1);
            cout<<s1[i];
        }
        else if(c[i][j] == c[i - 1][j])print(i - 1, j);
        else print(i, j - 1);
    }
    int main()
    {
        //最优子结构状态值初始化
        memset(c, 0, sizeof(c));
        //输入序列s1和s2的长度
        cin>>len1>>len2;
        //输入需要求最长公共子序列的序列s1和s2
        cin>>s1+1>>s2+1;  
        for(int i = 1; i <= len1; i ++){
            for(int j = 1; j <= len2; j ++){
                if(s1[i] == s2[j])c[i][j] = c[i - 1][j - 1] + 1;
                else c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
        print(len1, len2);
        //cout<<c[len1][len2]<<'\n';
        return 0;
    }
    

    方二、闫氏DP分析法(从集合的角度考虑):

    分析:

    很久之前在Acwing上学习后,写的题解(字丑):

    我们通过f[i] [j]去表示所有A[1 ~ i]和B[1 ~ j]的公共子序列的集合,其表示的属性是最大值(即最长长度)。

    我们通过最长公共子序列是否包含最后两个元素即a[i]和b[j]对这个集合来进行划分,可以分为4种情况:

    1. a[i]和b[j]相等
    2. a[i]和b[j]不相等,a[i]和bx匹配x在j之前
    3. a[i]和b[j]不相等,b[j]和ax匹配x在i之前
    4. a[i]和b[j]不相等,两数都没有匹配

    对于f[i] [j] = f[i - 1] [j - 1] + 1覆盖情况1

    对于f[i] [j] = max{f[i - 1] [j], f[i] [j - 1]}覆盖情况2 3 4

    请添加图片描述
    请添加图片描述

    代码:

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    using namespace std;
    int n,m,f[1005][1005];
    char s1[1005],s2[1005];
    int main()
    {
        cin>>n>>m;
        cin>>s1+1>>s2+1;//从下标1开始存入s1和s2
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1;//此位置两个元素相同
                else f[i][j]=max(f[i][j-1],f[i-1][j]); //此时两个元素不同
            }
        }
        cout<<f[n][m]<<endl;
        return 0;
    }
    
    //状态表示:f[i][j]是以1~ai的序列和以1~bj的序列的最长的公共子序列长度
    
    //当枚举到的两个元素相同时:
    //说明可以将该元素加入到两个子序列的最长公共子序列上,因此就直接对于f[i][j]=f[i-1][j-1]+1,表示在1~a[i-1]和
    //1~b[j-1]的公共最长子序列的基础上加1,将f[i-1][j-1]状态加一转移给f[i][j]
    //因此我们转移公式就是:f[i][j]=f[i-1][j-1]+1
    
    //当枚举到的两个元素不同:
    //那我们肯定是不能够将他们加入到两个子序列的最长公共子序列上,因此我们要去寻找之前最长的公共子序列长度转移过来
    //对于a[i]和b[j]不相等存在3中情况:
    //1、a[i]属于a和b的最长公共子序列,a[i]和bx匹配x在j之前,那么我们就要从f[i][j-1]将状态转移过来,此时的状态就
    //是到i,j为止最长的公共子序列长度
    //2、b[j]属于a和b的最长公共子序列,b[j]和ax匹配x在i之前,那么我们就要从f[i-1][j]将状态转移过来此时的状态就是
    //到i,j为止最长的公共子序列长度
    //3、a[i]和b[j]都不属于a和b的最长公共子序列,我们应当是从f[i-1][j-1]去将状态转移过来,但对于f[i-1][j]和f[i][j-1]
    //是已经将f[i-1][j-1]的状态包括在里面(因为这三者是相等的)
    //因此我们转移公式就是:f[i][j]=max(f[i][j-1],f[i-1][j])
    
    更多相关内容
  • 最长公共子序列(Longest Common Subsequence LCS)是从给定的两个序列X和Y中取出尽可能多的一部分字符,按照它们在原序列排列的先后次序排列得到。LCS问题的算法用途广泛,如在软件不同版本的管理中,用LCS算法找到...
  • 最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个。子串是要求更严格的一种子序列,要求在母串中连续地出现。在上述例子的中,最长公共子序列为blog(cnblogs, ...
  • 主要介绍了Java基于动态规划法实现求最长公共子序列及最长公共子字符串,简单描述了动态规划法的概念、原理,并结合实例形式分析了Java使用动态规划法求最长公共子序列以及最长公共子字符串相关实现技巧,需要的朋友...
  • 则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二、算法求解 这是一个动态规划的题目。对于可用动态规划求解的问题,一般有两个特征:①最优子结构;②重叠子问题 ①最优子结构 设X=(x1,x2,…,xn)...
  • 【问题描述】使用动态规划算法解最长公共子序列问题,具体来说就是,依据其递归式自底向上的方式依次计算得到每个子问题的最优值。 【输入形式】在屏幕上输入两个序列X和Y,序列各元素数间都以一个空格分隔。 ...
  • 最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1...
  • 算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
  • 1、题目描述 2、代码详解 自下向上 class Solution(object): # Modify the original triangle, bottom-up def minimumTotal(self, triangle): """ :type triangle: List[List[int]] :rtype: int ...
  • 用c++语言写的最长公共子序列问题,比较经典的动态规划问题。能完美运行,输入2个字符串序列之后就能得出最长公共子序列
  • 利用动态规划法求出两个序列的最长公共子序列,内含C++源代码和实验报告
  • 所有最长公共子序列(LCS)——动态规划——Java---所有!!!所有!!!所有!!!
  • 在大数据时代,这些序列的长度和大小呈爆炸性增长,这给经典的NP-hard问题带来了巨大挑战,即从多个序列中搜索多个最长公共子序列(MLCS)。 在本文中,我们首先揭露了最新的MLCS算法无法应用于长距离和大规模序列...
  • 算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 ...(包括输入格式、算法、输出格式) ...(除了截图外,实验结果还用图表进行了分析) ...
  • %%%输入%%%X, Y - 都是字符串,例如 'test' 或 'stingtocompare' %%%输出%%%D 是最短字符串长度上的字符串%%%dist 是子串的长度%%%aLongestString 是一个长度为 dist 的字符串(可能只有一个)
  • 最长公共子序列

    2014-06-26 10:46:45
    1. 最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=, x2,…, xm>,则另一序列Z=, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 , i2,…, ik>,使得...
  • NULL 博文链接:https://lisajoy512.iteye.com/blog/1231823
  • 分步讲解 最长公共子序列求法 1在Excel中找到规律 2规律总结到程序中 3根据规律找到长度 4找到长度的规律 5长度对应的值及对应的公共子序列 这个算法可以应用到文字录入测试的应用中,测试文字录入内容,常用的...
  • 用Python实现动态规划中最长公共子序列和最长公共子串问题!
  • 主要为大家详细介绍了python实现最长公共子序列的相关代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 73、1265:【例9.9】最长公共子序列(2020.02.09)-A
  • 主要介绍了Ruby实现的最长公共子序列算法,本文直接给出实现代码,需要的朋友可以参考下
  • 本科算法实验-最长公共子序列【数据+代码+说明+流程图+测试用例】
  • C语言求最长公共子序列问题的算法实现。LCS问题,没有太多的描述语言了,这个资源很简单的。
  • 关于动态规划算法的最长公共子序列的Java代码,帮助了解算法实现过程

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,856
精华内容 17,142
关键字:

最长公共子序列