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

    千次阅读 2019-10-24 15:17:31
    最长公共子序列

    最长公共子序列 

    最长公共子序列 Longest Common Sequence(LCS) 

     

     

     

     

     

    /// LCS问题
    /// 动态规划
    /// 时间复杂度: O(len(s1)*len(s2))
    /// 空间复杂度: O(len(s1)*len(s2))
    public class LCS1 {
        private int[][] memo;
        public String lcs(String s1, String s2) {
            if (s1 == null || s2 == null) {
                throw new IllegalArgumentException("s1 and s2 can not be null.");
            }
            if (s1.length() == 0 || s2.length() == 0) {
                return "";
            }
            memo = new int[s1.length()][s2.length()];
            for (int i = 0; i < s1.length(); i++) {
                Arrays.fill(memo[i], -1);
            }
            lcs(s1, s2, s1.length() - 1, s2.length() - 1);
            return getLCS(s1, s2);
        }
        // 求s1[0...m]和s2[0...n]的最长公共子序列的长度值
        private int lcs(String s1, String s2, int m, int n) {
            if (m < 0 || n < 0) {
                return 0;
            }
            if (memo[m][n] != -1) {
                return memo[m][n];
            }
            int res = 0;
            if (s1.charAt(m) == s2.charAt(n)) {
                res = 1 + lcs(s1, s2, m - 1, n - 1);
            } else {
                res = Math.max(lcs(s1, s2, m - 1, n), lcs(s1, s2, m, n - 1));
            }
            memo[m][n] = res;
            return res;
        }
        // 通过memo反向求解s1和s2的最长公共子序列
        private String getLCS(String s1, String s2) {
            int m = s1.length() - 1;
            int n = s2.length() - 1;
            StringBuilder res = new StringBuilder("");
            while (m >= 0 && n >= 0) {
                if (s1.charAt(m) == s2.charAt(n)) {
                    res = res.insert(0, s1.charAt(m));
                    m--;
                    n--;
                } else if (m == 0) {
                    n--;
                } else if (n == 0) {
                    m--;
                } else {
                    if (memo[m - 1][n] > memo[m][n - 1]) {
                        m--;
                    } else {
                        n--;
                    }
                }
            }
            return res.toString();
        }
        //public static void main(String[] args) {
        //    String s1 = "ABCDGH";
        //    String s2 = "AEDFHR";
        //    System.out.println((new LCS1()).lcs(s1, s2));
        //    s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
        //    s2 = "CACCCCTAAGGTACCTTTGGTTC";
        //    System.out.println((new LCS1()).lcs(s1, s2));
        //}
    }
    /// LCS问题
    /// 动态规划
    /// 时间复杂度: O(len(s1)*len(s2))
    /// 空间复杂度: O(len(s1)*len(s2))
    public class LCS2 {
        public String lcs(String s1, String s2){
            int m = s1.length();
            int n = s2.length();
            // 对memo的第0行和第0列进行初始化
            int[][] memo = new int[m][n];
            for(int j = 0 ; j < n ; j ++) {
                if(s1.charAt(0) == s2.charAt(j)){
                    for(int k = j ; k < n ; k ++) {
                        memo[0][k] = 1;
                    }
                    break;
                }
            }
            for(int i = 0 ; i < m ; i ++) {
                if(s1.charAt(i) == s2.charAt(0)) {
                    for(int k = i ; k < m ; k ++) {
                        memo[k][0] = 1;
                    }
                    break;
                }
            }
            // 动态规划的过程
            for(int i = 1 ; i < m ; i ++) {
                for(int j = 1 ; j < n ; j ++) {
                    if(s1.charAt(i) == s2.charAt(j)) {
                        memo[i][j] = 1 + memo[i-1][j-1];
                    } else {
                        memo[i][j] = Math.max(memo[i-1][j], memo[i][j-1]);
                    }
                }
            }
            // 通过memo反向求解s1和s2的最长公共子序列
            m = s1.length() - 1;
            n = s2.length() - 1;
            StringBuilder res = new StringBuilder("");
            while(m >= 0 && n >= 0) {
                if(s1.charAt(m) == s2.charAt(n)){
                    res.insert(0, s1.charAt(m));
                    m --;
                    n --;
                }
                else if(m == 0) {
                    n --;
                } else if(n == 0) {
                    m --;
                } else{
                    if(memo[m-1][n] > memo[m][n-1]) {
                        m --;
                    } else {
                        n --;
                    }
                }
            }
            return res.toString();
        }
        //public static void main(String[] args) {
        //    String s1 = "ABCDGH";
        //    String s2 = "AEDFHR";
        //    System.out.println((new LCS2()).lcs(s1, s2));
        //    s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
        //    s2 = "CACCCCTAAGGTACCTTTGGTTC";
        //    System.out.println((new LCS2()).lcs(s1, s2));
        //}
    }
    /// LCS问题
    /// 动态规划, 躲避边界条件
    /// 时间复杂度: O(len(s1)*len(s2))
    /// 空间复杂度: O(len(s1)*len(s2))
    public class LCS3 {
        public String lcs(String s1, String s2){
            int m = s1.length();
            int n = s2.length();
            // memo 是 (m + 1) * (n + 1) 的动态规划表格
            // memo[i][j] 表示s1的前i个字符和s2前j个字符的最长公共子序列的长度
            // 其中memo[0][j] 表示s1取空字符串时, 和s2的前j个字符作比较
            // memo[i][0] 表示s2取空字符串时, 和s1的前i个字符作比较
            // 所以, memo[0][j] 和 memo[i][0] 均取0
            // 我们不需要对memo进行单独的边界条件处理 :-)
            int[][] memo = new int[m + 1][n + 1];
            // 动态规划的过程
            // 注意, 由于动态规划状态的转变, 下面的i和j可以取到m和n
            for(int i = 1 ; i <= m ; i ++) {
                for(int j = 1 ; j <= n ; j ++) {
                    if(s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        memo[i][j] = 1 + memo[i - 1][j - 1];
                    } else {
                        memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
                    }
                }
            }
            // 通过memo反向求解s1和s2的最长公共子序列
            m = s1.length();
            n = s2.length();
            StringBuilder res = new StringBuilder("");
            while(m > 0 && n > 0) {
                if(s1.charAt(m - 1) == s2.charAt(n - 1)){
                    res.insert(0, s1.charAt(m - 1));
                    m --;
                    n --;
                }
                else if(memo[m - 1][n] > memo[m][n - 1]) {
                    m --;
                } else {
                    n --;
                }
            }
            return res.toString();
        }
        //public static void main(String[] args) {
        //    String s1 = "ABCDGH";
        //    String s2 = "AEDFHR";
        //    System.out.println((new LCS3()).lcs(s1, s2));
        //    s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
        //    s2 = "CACCCCTAAGGTACCTTTGGTTC";
        //    System.out.println((new LCS3()).lcs(s1, s2));
        //}
    }

     

    展开全文
  • 动态规划 最长公共子序列 过程图解

    万次阅读 多人点赞 2016-05-29 22:54:25
     首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后...

    1.基本概念

          首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢?给定串中任意个连续的字符组成的子序列称为该串的子串。给一个图再解释一下:


           如上图,给定的字符序列: {a,b,c,d,e,f,g,h},它的子序列示例: {a,c,e,f} 即元素b,d,g,h被去掉后,保持原有的元素序列所得到的结果就是子序列。同理,{a,h},{c,d,e}等都是它的子序列。
           它的字串示例:{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的字串。同理,{a,b,c,d},{g,h}等都是它的字串。

            这个问题说明白后,最长公共子序列(以下都简称LCS)就很好理解了。
    给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。
    s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}

    2.动态规划

           求解LCS问题,不能使用暴力搜索方法。一个长度为n的序列拥有 2的n次方个子序列,它的时间复杂度是指数阶,太恐怖了。解决LCS问题,需要借助动态规划的思想。
           动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。

    3.特征分析

           解决LCS问题,需要把原问题分解成若干个子问题,所以需要刻画LCS的特征。

           设A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”为它们的最长公共子序列。不难证明有以下性质:
           如果am=bn,则zk=am=bn,且“z0,z1,…,z(k-1)”是“a0,a1,…,a(m-1)”和“b0,b1,…,b(n-1)”的一个最长公共子序列;
           如果am!=bn,则若zk!=am,蕴涵“z0,z1,…,zk”是“a0,a1,…,a(m-1)”和“b0,b1,…,bn”的一个最长公共子序列;
           如果am!=bn,则若zk!=bn,蕴涵“z0,z1,…,zk”是“a0,a1,…,am”和“b0,b1,…,b(n-1)”的一个最长公共子序列。

           有些同学,一看性质就容易晕菜,所以我给出一个图来让这些同学理解一下:


           以我在第1小节举的例子(S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}),并结合上图来说:

           假如S1的最后一个元素 与 S2的最后一个元素相等,那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS  再加上 S1和S2相等的最后一个元素。

           假如S1的最后一个元素 与 S2的最后一个元素不等(本例子就是属于这种情况),那么S1和S2的LCS就等于 : {S1减去最后一个元素} 与 S2 的LCS, {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

    4.递归公式

            第3节说了LCS的特征,我们可以发现,假设我需要求 a1 ... am 和 b1 .. b(n-1)的LCS 和 a1 ... a(m-1) 和 b1 .. bn的LCS,一定会递归地并且重复地把如a1... a(m-1) 与 b1 ... b(n-1) 的 LCS 计算几次。所以我们需要一个数据结构来记录中间结果,避免重复计算。

            假设我们用c[i,j]表示Xi 和 Yj 的LCS的长度(直接保存最长公共子序列的中间结果不现实,需要先借助LCS的长度)。其中X = {x1 ... xm},Y ={y1...yn},Xi = {x1 ... xi},Yj={y1... yj}。可得递归公式如下:

             

    5.计算LCS的长度

           这里我不打算贴出相应的代码,只想把这个过程说明白。还是以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。我们借用《算法导论》中的推导图:


             图中的空白格子需要填上相应的数字(这个数字就是c[i,j]的定义,记录的LCS的长度值)。填的规则依据递归公式,简单来说:如果横竖(i,j)对应的两个元素相等,该格子的值 = c[i-1,j-1] + 1。如果不等,取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化该表:

             

              然后,一行一行地从上往下填:

             

              S1的元素3 与 S2的元素3 相等,所以 c[2,1] = c[1,0] + 1。继续填充:

              

                S1的元素3 与 S2的元素5 不等,c[2,2] =max(c[1,2],c[2,1]),图中c[1,2] 和 c[2,1] 背景色为浅黄色。

                继续填充:

                

                

                 

                   中间几行填写规则不变,直接跳到最后一行:

                  

                    至此,该表填完。根据性质,c[8,9] = S1 和 S2 的 LCS的长度,即为5。

    6.构造LCS

           本文S1和S2的最LCS并不是只有1个,本文并不是着重讲输出两个序列的所有LCS,只是介绍如何通过上表,输出其中一个LCS。

           我们根据递归公式构建了上表,我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。

           c[8][9] = 5,且S1[8] != S2[9],所以倒推回去,c[8][9]的值来源于c[8][8]的值(因为c[8][8] > c[7][9])。

           c[8][8] = 5,  且S1[8] = S2[8], 所以倒推回去,c[8][8]的值来源于 c[7][7]。

           以此类推,如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)。

           第一种结果为:

           

              这就是倒推回去的路径,棕色方格为相等元素,即LCS = {3,4,6,7,8},这是其中一个结果。

              如果如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,选择另一个方向,会得到另一个结果。

              

               即LCS ={3,5,7,7,8}。

    7.关于时间复杂度

            构建c[i][j]表需要Θ(mn),输出1个LCS的序列需要Θ(m+n)。


              本文内容参考如下:

            【1】http://baike.baidu.com/link?url=iKrtEZXAQ3LeQLL7Z0HQWpy7EO7BZInUR17C63lAIDFBJ_COm8e3KmKVxQCD6DlOvji2F9W6achz49Z_anZCfa

            【2】《算法导论》第3版 15.4节


            注意:
            如您发现本文档中有明显错误的地方,
            或者您发现本文档中引用了他人的资料而未进行说明时,请联系我进行更正。
            转载或使用本文档时,请作醒目说明。
            必要时请联系作者,否则将追究相应的法律责任。

            note:
            If you find this document with any error ,
            Or if you find any illegal citations , please contact me correct.
            Reprint or use of this document,Please explain for striking. 
            Please contact the author if necessary, or they will pursue the corresponding legal responsibility.



    展开全文
  • 动态规划解最长公共子序列(LCS)(附详细填表过程)

    万次阅读 多人点赞 2018-11-20 12:51:34
    最长公共子序列(以下简称LCS): 方法 蛮力法求解最长公共子序列: 动态规划求解最长公共子序列: 分析规律: 做法: 伪代码: 下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例): 时间复杂度...

    目录

    相关概念

    子序列形式化定义:

    公共子序列定义:

    最长公共子序列(以下简称LCS):

    方法

    蛮力法求解最长公共子序列:

    动态规划求解最长公共子序列:

    分析规律:

    做法:

    伪代码:

    下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例):

    时间复杂度:

    代码:

    结果示例:


    相关概念

    子序列形式化定义:

    给定一个序列X=<x1,x2,x3,x4...,xm>,另一个序列Z=<z1,z2,z3,z4...,zk>,若存在一个严格递增的X的下标序列<i1,i2,i3,...,ik>对所有的1,2,3,...,k,都满足x(ik)=zk,则称Z是X的子序列

    比如Z=<B,C,D,B>是X=<A,B,C,B,D,A,B>的子序列

    公共子序列定义:

    如果Z既是X的子序列,又是Y的子序列,则称Z为X和Y的公共子序列

    最长公共子序列(以下简称LCS):

    2个序列的子序列中长度最长的那个

    方法

    蛮力法求解最长公共子序列:

    需要遍历出所有的可能,时间复杂度是O(n³),太慢了

    动态规划求解最长公共子序列:

    分析规律:

    设X=<x1,x2,x3,x4...,xm>,Y=<y1,y2,y3,y4...,yn>为两个序列,Z=<z1,z2,z3,z4...,zk>是他们的任意公共子序列

    经过分析,我们可以知道:

    1、如果xm = yn,则zk = xm = yn 且 Zk-1是Xm-1和Yn-1的一个LCS

    2、如果xm != yn 且 zk != xm,则Z是Xm-1和Y的一个LCS

    3、如果xm != yn 且 zk != yn,则Z是X和Yn-1的一个LCS

    所以如果用一个二维数组c表示字符串X和Y中对应的前i,前j个字符的LCS的长度话,可以得到以下公式:

    文字意思就是:

    p1表示X的前 i-1 个字符和Y的前 j 个字符的LCS的长度

    p2表示X的前 i 个字符和Y的前 j-1 个字符的LCS的长度

    p表示X的前 i-1 个字符和Y的前 j-1 个字符的LCS的长度

    p0表示X的前 i 个字符和Y的前 j 个字符的LCS的长度

    如果X的第 i 个字符和Y的第 j 个字符相等,则p0 = p + 1

    如果X的第 i 个字符和Y的第 j 个字符不相等,则p0 = max(p1,p2)

     

    做法:

    因此,我们只需要从c[0][0]开始填表,填到c[m-1][n-1],所得到的c[m-1][n-1]就是LCS的长度

    但是,我们怎么得到LCS本身而非LCS的长度呢?

    也是用一个二维数组b来表示:

    在对应字符相等的时候,用↖标记

    在p1 >= p2的时候,用↑标记

    在p1 < p2的时候,用←标记

    伪代码:

    若想得到LCS,则再遍历一次b数组就好了,从最后一个位置开始往前遍历:

    如果箭头是↖,则代表这个字符是LCS的一员,存下来后 i-- , j--

    如果箭头是←,则代表这个字符不是LCS的一员,j--

    如果箭头是↑ ,也代表这个字符不是LCS的一员,i--

    如此直到i = 0或者j = 0时停止,最后存下来的字符就是所有的LCS字符

    比如说求ABCBDAB和BDCABA的LCS:

    灰色且带↖箭头的部分即为所有的LCS的字符

     

    下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例):

    以此类推

    最后填出的表为:

    右下角的2即为LCS的长度

     

    时间复杂度:

    由于只需要填一个m行n列的二维数组,其中m代表第一个字符串长度,n代表第二个字符串长度

    所以时间复杂度为O(m*n)

    代码:

    #include <iostream>
    #include <string>
    #include <stack>
    using namespace std;
    void LCS(string s1,string s2)
    {
        int m=s1.length()+1;
        int n=s2.length()+1;
        int **c;
        int **b;
        c=new int* [m];
        b=new int* [m];
        for(int i=0;i<m;i++)
        {
            c[i]=new int [n];
            b[i]=new int [n];
            for(int j=0;j<n;j++)
                b[i][j]=0;
        }
        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=0;i<m-1;i++)
        {
            for(int j=0;j<n-1;j++)
            {
                if(s1[i]==s2[j])
                {
                    c[i+1][j+1]=c[i][j]+1;
                    b[i+1][j+1]=1;          //1表示箭头为  左上
                }
                else if(c[i][j+1]>=c[i+1][j])
                {
                    c[i+1][j+1]=c[i][j+1];
                    b[i+1][j+1]=2;          //2表示箭头向  上
                }
                else
                {
                    c[i+1][j+1]=c[i+1][j];
                    b[i+1][j+1]=3;          //3表示箭头向  左
                }
            }
        }
        for(int i=0;i<m;i++)                //输出c数组
        {
            for(int j=0;j<n;j++)
            {
                cout<<c[i][j]<<' ';
            }
            cout<<endl;
        }
        stack<char> same;                   //存LCS字符
        stack<int> same1,same2;             //存LCS字符在字符串1和字符串2中对应的下标,方便显示出来
        for(int i = m-1,j = n-1;i >= 0 && j >= 0; )
        {
            if(b[i][j] == 1)
            {
                i--;
                j--;
                same.push(s1[i]);
                same1.push(i);
                same2.push(j);
            }
            else if(b[i][j] == 2)
                    i--;
                 else
                    j--;
        }
        cout<<s1<<endl;                     //输出字符串1
        for(int i=0;i<m && !same1.empty();i++)      //输出字符串1的标记
        {
            if(i==same1.top())
            {
                cout<<1;
                same1.pop();
            }
            else
                cout<<' ';
        }
        cout<<endl<<s2<<endl;                //输出字符串2
        for(int i=0;i<n && !same2.empty();i++)      //输出字符串2的标记
        {
            if(i==same2.top())
            {
                cout<<1;
                same2.pop();
            }
            else
                cout<<' ';
        }
        cout<<endl<<"最长公共子序列为:";
        while(!same.empty())
        {
            cout<<same.top();
            same.pop();
        }
        cout<<endl<<"长度为:"<<c[m-1][n-1]<<endl;
        for (int i = 0; i<m; i++)
        {
            delete [] c[i];
            delete [] b[i];
        }
        delete []c;
        delete []b;
    }
    int main()
    {
        string s1="ABCPDSFJGODIHJOFDIUSHGD";
        string s2="OSDIHGKODGHBLKSJBHKAGHI";
        LCS(s1,s2);
        return 0;
    }
    

    结果示例:

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,189
精华内容 5,675
关键字:

最长公共子序列