最长公共子序列LCS(动态规划)—详解

标签: 算法  c/c++

一.基本概念

1、 子序列(subsequence): 一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。例如序列<A,B,C,B,D,A,B><A,B,C,B,D,A,B>的子序列有:<A,B><A,B>、<B,C,A><B,C,A>、<A,B,C,D,A><A,B,C,D,A>等。

2、公共子序列(common subsequence): 给定序列X和Y,序列Z是X的子序列,也是Y的子序列,则Z是X和Y的公共子序列。例如X=<A,B,C,B,D,A,B>X=<A,B,C,B,D,A,B>,Y=<B,D,C,A,B,A>Y=<B,D,C,A,B,A>,那么序列Z=<B,C,A>Z=<B,C,A>为X和Y的公共子序列,其长度为3。但ZZ不是XX和YY的最长公共子序列,而序列<B,C,B,A><B,C,B,A>和<B,D,A,B><B,D,A,B>也均为XX和YY的最长公共子序列,长度为4,而XX和YY不存在长度大于等于5的公共子序列。

3、最长公共子序列问题(LCS:longest-common-subsequence problem):In the longest-common-subsequence problem, we are given two sequences X=<x1,x2,…,xm>X=<x1,x2,…,xm> and Y=<y1,y2,…,yn>Y=<y1,y2,…,yn> and wish to find a (not “the”) maximum-length common subsequence of XX and YY . This section shows how to efficiently solve the LCS problem using dynamic programming.

其次科普一下,最长公共子序列(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}

二.最长公共子序列解决方案

方案1:蛮力搜索策略
蛮力搜索策略的步骤如下:

  • 枚举序列XX里的每一个子序列xixi;
  • 检查子序列xixi是否也是YY序列里的子序列;
  • 在每一步记录当前找到的子序列里面的最长的子序列。

蛮力策略也叫做暴力穷举法,是所有算法中最直观的方法,但效率往往也是最差的。在第1步枚举XX中所有的子序列有2m2m个,每个子序列在YY中检查时间复杂度为O(n)O(n)。因此蛮力策略的最坏时间复杂度为O(n2m)O(n2m),这是指数级算法,对较长的序列求LCS是不适用的。

2.动态规划

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

特征分析

解决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}。可得递归公式如下:
C[i,j]={0 若 i=0 或 j=0C[i1,j1]+1 若 i,j>0,xi=yjmax{C[i,j1],C[i1,j]} 若 i,j>0,xiyjC[i, j]=\left\{\begin{array}{ll}0 & \text { 若 } i=0 \text { 或 } j=0 \\ C[i-1, j-1]+1 & \text { 若 } i, j>0, x_{i}=y_{j} \\ \max \{C[i, j-1], C[i-1, j]\} & \text { 若 } i, j>0, x_{i} \neq y_{j}\end{array}\right.

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。

构造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}。

关于时间复杂度

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

代码实现

#include <iostream>

using namespace std;

/*
* 这里可以不定义长度,输入的字符串用string存储,然后利用string.c_str()来对字符串进行数组转化。 我这里为了方便没有这样做。
*/
#ifndef MAX_LENGTH
#define MAX_LENGTH 15 //定义字符串最大长度
#endif

int MaxNum(int firstNum, int secondNum){
    return firstNum > secondNum ? firstNum : secondNum;
}

//定义数组结构体
struct matrix{
    int num;
    int direct;
};

typedef matrix Matrix;

int LCS(char *strA, char *strB, int lengthA, int lengthB, Matrix *resultMatrix[]){
    if (lengthA == 0 || lengthB == 0) {
        return 0;
    }
    for (int i = 0; i < lengthA; i++) {
        for (int j = 0; j < lengthB; j++) {
            resultMatrix[i][j].num = 0; //设置所有默认的最长为0
            resultMatrix[i][j].direct = 1; //所有默认方向变成上 0斜上,1上,-1左
        }
    }

    for (int i = 0; i < lengthA; i++) {
        for (int j = 0; j < lengthB; j++) {
            if (strA[i] == strB[j]) {
                resultMatrix[i+1][j+1].num = resultMatrix[i][j].num + 1;
                resultMatrix[i+1][j+1].direct = 0;
            }else{
                resultMatrix[i+1][j+1].num = MaxNum(resultMatrix[i+1][j].num, resultMatrix[i][j+1].num);
                resultMatrix[i+1][j+1].direct = resultMatrix[i+1][j].num > resultMatrix[i][j+1].num ? 1 : -1;
            }
        }
    }
    return resultMatrix[lengthA][lengthB].num;
}

int main(int argc, const char * argv[]) {
    char *strA = (char*)malloc(sizeof(char) * MAX_LENGTH);
    char *strB = (char*)malloc(sizeof(char) * MAX_LENGTH);
    scanf("%s",strA);
    scanf("%s",strB);
    int lengthA = (int)strlen(strA);
    int lengthB = (int)strlen(strB);
    Matrix *resultMatrix[lengthA+1];
    for (int i = 0; i <= lengthA; i++) {
        resultMatrix[i] = (Matrix*)malloc(sizeof(struct matrix)* (lengthB+1));
    }

    int max = LCS(strA, strB, lengthA, lengthB, resultMatrix);
    printf("%d\n",max);
    std::cout << "Hello, World!\n";
    return 0;
}

参考自:
Running07

版权声明:本文为weixin_44023658原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44023658/article/details/105998262

智能推荐

SpringBoot 使用freemarker 处理文档,找不到文件位置(报错:basePackagePath=““ /* relatively to resourceLoaderClass pkg)

在Spring Boot中加载word的文档的时候,加载ftl文档的位置应该是从 target目录下面去加载的(不太确定),不是像大多数情况这样根据类的路径去加载。SpringBoot加载的位置应该是从 “resources”文件下面开始,如果放到“resources”的根目录下面需要加一道“/”斜线。 类似于: config...

剑指offer 合并两个排序的链表

题目 链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/ 思路 我想的是,与合并两个有序数组一样的思维,新建一个链表,然后判断谁的值大,进而在新的链表上面进行插入。 看书思路 合并链表是一个递归问题:合并一个节点后可以转化为一个子问题。终止条件是其中一个链表为空 代码 链表反转也可以用递归解决...

Java编程思想 第三章:操作符

Java中的操作符和c/c++中的操作符基本一致,因为我之前学习过C语言和C++,所以本章的内容大部分都已熟知,下面只做简单的介绍。 Java操作符及优先级 Java中的操作符包括算术操作符,关系操作符,逻辑操作符,位运算符、自操作运算符、移位运算符、赋值运算符和其他运算符。 算术操作符:包括加减乘除和取余(%),优先级乘除取余高于加减,都是双元运算符,其中加法(+)可以用来连接两个字符串,比如:...

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

猜你喜欢

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...