C++动态规划实现查找最长公共子序列

目录
  • 最长公共子序列
  • 代码实现
  • 结果

最长公共子序列

最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。

动态规划：

采用二维数组flag来记录下标i和j的走向。数字"1"表示，斜向下；数字"2"表示，水平向右；数字"3"表示，竖直向下

问题描述： 设有字符串a[0…n]，b[0…m]，下面就是递推公式。字符串a对应的是二维数组num的行，字符串b对应的是二维数组num的列。

代码实现

#include<stdio.h>
#include<string.h>
char a[500],b[500];
char num[501][501]; ///记录中间结果的数组
char flag[501][501];    ///标记数组，用于标识下标的走向，构造出公共子序列
void LCS(); ///动态规划求解
void getLCS();    ///采用倒推方式求最长公共子序列
int main()
{
    int i;
    strcpy(a,"ABCBDAB");
    strcpy(b,"BDCABA");
    memset(num,0,sizeof(num));
    memset(flag,0,sizeof(flag));
    LCS();
    printf("%d\n",num[strlen(a)][strlen(b)]);
    getLCS();
    return 0;
}
void LCS()
{
    int i,j;
    for(i=1;i<=strlen(a);i++)
    {
        for(j=1;j<=strlen(b);j++)
        {
            if(a[i-1]==b[j-1])   ///注意这里的下标是i-1与j-1
            {
                num[i][j]=num[i-1][j-1]+1;
                flag[i][j]=1;  ///斜向下标记
            }
            else if(num[i][j-1]>num[i-1][j])
            {
                num[i][j]=num[i][j-1];
                flag[i][j]=2;  ///向右标记
            }
            else
            {
                num[i][j]=num[i-1][j];
                flag[i][j]=3;  ///向下标记
            }
        }
    }
}
void getLCS()
{
    char res[500];
    int i=strlen(a);
    int j=strlen(b);
    int k=0;    ///用于保存结果的数组标志位
    while(i>0 && j>0)
    {
        if(flag[i][j]==1)   ///如果是斜向下标记
        {
            res[k]=a[i-1];
            k++;
            i--;
            j--;
        }
        else if(flag[i][j]==2)  ///如果是斜向右标记
            j--;
        else if(flag[i][j]==3)  ///如果是斜向下标记
            i--;
    }
    for(i=k-1;i>=0;i--)
        printf("%c",res[i]);
}

结果

时间复杂度：

由于只需要填一个m行n列的二维数组，其中m代表第一个字符串长度，n代表第二个字符串长度，所以时间复杂度为O（m*n）。

到此这篇关于C++动态规划实现查找最长公共子序列的文章就介绍到这了,更多相关C++最长公共子序列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++ 动态规划算法使用分析

    C++ 动态规划算法使用分析

    目录 Fibonacci 字符串分割(Word Break) 三角矩阵(Triangle) 路径总数(Unique Paths) 最小路径和(Minimum Path Sum) Fibonacci 题目描述: 大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项. 解题思路: 1.递归 2.动态规划 状态:F(n) 状态递推:F(n)=F(n-1)+F(n-2) 初始值:F(1)=F(2)=1 返回结果:F(N) 代码实现: 法一:递归(效率低): class

  • C++动态规划之背包问题解决方法

    本文实例讲述了C++动态规划之背包问题解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 背包的最大容量为W,有N件物品,每件物品重量为w,价值为p,怎样选择物品能使得背包里的物品价值最大? 输入: 10 3   (W,N) 4 5   (w,p) 6 7   (w,p) 8 9   (w,p) 实现代码: #include <stdio.h> #define THING 20 #define WEIGHT 100 int arr[THING][WEIGHT]; /* 背包容量为wei

  • c++动态规划经典算法

    c++动态规划经典算法

    目录 基本思想 重要分析问题方法 动态规划算法实例 1.台阶问题 2.从矩阵左上角走到右下角最短路径问题 3.最大子数组问题 4.最长公共子序列 基本思想 动态规划算法通常用于求解具有某种最优性质的问题.在这类问题中,可能会有许多可行解.每一个解都对应于一个值,我们希望找到具有最优值的解.动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解.与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的.若用分

  • C++动态规划之最长公子序列实例

    本文实例讲述了C++动态规划之最长公子序列解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 求出两个字符串中的最长公子序列的长度. 输入: csblog belong 输出: max length = 4 实现代码: #include <stdio.h> #include <string.h> int arr[200][200]; /* 表示str1的前i位和str2的前j位的最长公子序列的长度 */ int main() { char str1[100],str2[10

  • C++动态规划计算最大子数组

    C++动态规划计算最大子数组

    目录 例题 1.求最大的子数组的和 2.求和最大的相应子数组 例题 题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为O(n). 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18. 1.求最大的子数组的和 代码[C++] #include <iostream> using namespace std

  • C++动态规划算法实现矩阵链乘法

    C++动态规划算法实现矩阵链乘法

    问题描述: 给定n个矩阵的链<A1,A2,…,An>,矩阵Ai的规模为p(i-1)×p(i) (1<=i<=n),求完全括号化方案,使得计算乘积A1A2…An所需标量乘法次数最少. 动态规划的第一步是寻找最优子结构,然后就可以利用这种子结构从子问题的最优解构造出原问题的最优解.在矩阵链乘法问题中,我们假设A(i)A(i+1)…A(j)的最优括号方案的分割点在A(k)和A(k+1)之间.那么,继续对“前缀”子链A(i)A(i+1)…A(k)进行括号化时,我们应该直接采用独立求解它时所

  • C++实现LeetCode(152.求最大子数组乘积)

    [LeetCode] 152. Maximum Product Subarray 求最大子数组乘积 Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has

  • C++编辑距离（动态规划）

    C++编辑距离（动态规划）

    题目描述: 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 . 我们可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 编辑距离:是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数.问题:word1到word2的编辑距离子问题:word1前i个字符到word2前j个字符的编辑距离假如有两个字符串"hat"和"wtct"每个格子表示word1前i个字符到word2前j个字符的编

  • C++实现LeetCode(53.最大子数组)

    [LeetCode] 53. Maximum Subarray 最大子数组 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1]

  • C++动态规划实现查找最长公共子序列

    C++动态规划实现查找最长公共子序列

    目录 最长公共子序列 代码实现 结果 最长公共子序列 最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题.一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列. 动态规划: 采用二维数组flag来记录下标i和j的走向.数字"1"表示,斜向下:数字"2"表示,水平向右:数字"3"表示,竖直向下 问题描述: 设有字符串a[0…n],b[0…m]

  • Python求两个字符串最长公共子序列代码实例

    一.问题描述 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence).比如字符串1:BDCABA:字符串2:ABCBDAB.则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二.算法求解 这是一个动态规划的题目.对于可用动态规划求解的问题,一般有两个特征:①最优子结构:②重叠子问题 ①最优子结构 设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X

  • 利用C++实现最长公共子序列与最长公共子串

    利用C++实现最长公共子序列与最长公共子串

    一.问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列.最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个.子串是要求更严格的一种子序列,要求在母串中连续地出现.在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共

  • Ruby实现的最长公共子序列算法

    最长公共子序列,LCS,动态规划实现. #encoding: utf-8 #author: xu jin, 4100213 #date: Nov 01, 2012 #Longest-Commom-Subsequence #to find a longest commom subsequence of two given character arrays by using LCS algorithm #example output: #The random character arrays are

  • Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例

    Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例

    本文实例讲述了Java基于动态规划法实现求最长公共子序列及最长公共子字符串.分享给大家供大家参考,具体如下: 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题.简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加. 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法. [问题] 求两字符序列的最长公共字符子序列 问题描述:字符

  • python实现最长公共子序列

    python实现最长公共子序列

    最长公共子序列python实现,最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来. 1.找出最优解的性质,并刻划其结构特征 序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么a[:m]和b[:n]的最长公共子序列长度就是a[:m-1]和b[:n-1]的最长公共子序列长度+1:如果a[m-1]!=b[n-1],那么a[:m]和b[:n]的最长公共子序列长度就是MAX(a[:m-1]和b[:n]的最长公共子序列长度,a[:m]和b[:n-1]的最长公共子序

  • Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法.分享给大家供大家参考,具体如下: 问题 输入 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列,如果有多个,随意输出1个. 输入示例 belong cnblogs 输出示例 blog 分析 既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法. 以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情

  • Java最长公共子序列示例源码

    最长公共子序列(Longest Common Subsequence)定义:两个或多个已知数列的子序列集合中最长的就是最长公共子序列.其实说到最长公共子序列,还有一个要提到的是最长公共子串(Longest Common Substring),它指的是两个字符串中的最长公共子串,要求子串一定连续.关于最长公共子串的内容我们后续也会讲到,今天先来看下最长公共子序列的相关内容. 之前看过一个LCS算法的实现过程,觉得太过繁琐.自己写了一个比较简单的,此处仅仅介绍实现过程. 程序代码测试通过,需要的童鞋

  • Java算法之最长公共子序列问题(LCS)实例分析

    Java算法之最长公共子序列问题(LCS)实例分析

    本文实例讲述了Java算法之最长公共子序列问题(LCS).分享给大家供大家参考,具体如下: 问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列.确切地说,若给定序列X= { x1, x2,-, xm},则另一序列Z= {z1, z2,-, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,-, ik},使得对于所有j=1,2,-,k有 Xij=Zj.例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,

  • javascript实现最长公共子序列实例代码

    javascript实现最长公共子序列实例代码

    介绍 最长公共子序列(Longest Common Subsequence LCS)是从给定的两个序列X和Y中取出尽可能多的一部分字符,按照它们在原序列排列的先后次序排列得到.LCS问题的算法用途广泛,如在软件不同版本的管理中,用LCS算法找到新旧版本的异同处;在软件测试中,用LCS算法对录制和回放的序列进行比较,在基因工程领域,用LCS算法检查患者DNA连与键康DNA链的异同;在防抄袭系统中,用LCS算法检查论文的抄袭率.LCS算法也可以用于程序代码相似度度量,人体运行的序列检索,视频段匹配等

随机推荐