精华内容
下载资源
问答
  • (为什么都更了这么多篇笔记了,这时候才...今后不排除你们还会看到最小生成树、背包等基础算法的笔记……)最长公共子序列(Longest Common Subsequence,LCS)是动态规划中的经典问题,顾名思义,即求两个序列最长...

    (为什么都更了这么多篇笔记了,这时候才讲这么基础的内容呢?因为我本来以为LCS这种简单的DP不用讲的,结果CF不久前考了LCS的变式,然后我发现由于自己对LCS一点都不熟,居然写不出来 ,于是决定还是写一下笔记。今后不排除你们还会看到最小生成树、背包等基础算法的笔记……)

    最长公共子序列(Longest Common Subsequence,LCS)是动态规划中的经典问题,顾名思义,即求两个序列最长的公共子序列(可以不连续)。在本文中,我们规定用

    表示序列
    的最后一个元素,用
    表示
    去掉最后一个元素后的子序列,
    表示s1和s2的LCS的长度。现在,假如我们有
    abdcbabbdcbabb两个字符串,记为
    ,我们要如何求它们的LCS呢?

    既然已经说了是动态规划问题,我们就考虑如何从子状态转移过来。这有两种情形,第一种,如果两个序列最后一个元素相同,比如abecbabbdcbabb,最后一个元素相同,所以它们的LCS长度就是abecbabdcbab的LCS长度加上1。这是因为,

    的任何公共子序列
    去掉最后一个元素后,都是
    的公共子序列,所以
    的长度不会大于

    ca22e61efa0862d4ba60de6d6335cbb0.png

    如果最后一个元素不同,则LCS长度应为

    ,因为这时两个序列的最后一个元素不会同时出现在LCS中。

    8bd11bf1cbe81c473a8eca8a80c6651e.png

    当然,我们还需要处理一下边界条件,即当

    中至少有一个为空时,这时LCS的长度为0。于是综合一下,我们可以得到以下式子:

    我们可以轻松地把它翻译成一个递归程序(我直接用Python写了):

    def lcs(s1,s2):
        if s1 == "" or s2 == "":
            return 0
        elif s1[-1] == s2[-1]:
            return lcs(s1[:-1], s2[:-1])+1
        else:
            return max(lcs(s1,s2[:-1]), lcs(s1[:-1],s2))

    然而,稍微了解一点递归的原理的人都知道,直接这样写,必然引起时间、空间复杂度的爆炸。于是我们可以用记忆化的方法,并且传参时传索引而不是序列本身。

    以下是HDU1159(LCS模板题)的AC代码:

    #include <algorithm>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int MAXN = 505;
    char s1[MAXN], s2[MAXN];
    int dp[MAXN][MAXN];
    int lcs(int n1, int n2)
    {
        if (dp[n1][n2] != -1)
            return dp[n1][n2];
        if (n1 == 0 || n2 == 0)
            dp[n1][n2] = 0;
        else if (s1[n1 - 1] == s2[n2 - 1])
            dp[n1][n2] = lcs(n1 - 1, n2 - 1) + 1;
        else
            dp[n1][n2] = max(lcs(n1, n2 - 1), lcs(n1 - 1, n2));
        return dp[n1][n2];
    }
    int main()
    {
        while (cin >> s1 >> s2)
        {
            memset(dp, -1, sizeof(dp));
            cout << lcs(strlen(s1), strlen(s2)) << endl;
        }
        return 0;
    }
    

    当然,为了节约栈空间,我们也可以用递推的方法,代码也很简洁:

    while (cin >> s1 >> s2)
    {
        memset(dp, 0, sizeof(dp));
        int n1 = strlen(s1), n2 = strlen(s2);
        for (int i = 1; i <= n1; ++i)
            for (int j = 1; j <= n2; ++j)
                if (s1[i - 1] == s2[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[n1][n2] << endl;
    }
    

    这一算法的时间复杂度和空间复杂度均为

    ,如果用滚动数组(即只维护两个一维数组,只保留
    dp[i]dp[i-1]中各项的值)可以把空间复杂度优化到

    输出方案

    例如,我们最终得到了这样一个二维数组:

    8ac9e97252c39fa4ad9dc4d36a68f427.png

    我们知道,如果某个dp[i][j]比它左上方的值大1,且s1[i-1]==s2[j-1](注意我这里用的是0-index所以要减1),说明可以选这个元素来增大LCS。于是我们可以用这样的策略:从右下角开始,如果有dp[i][j]==dp[i-1][j-1]+1则往左上走一格,如果同时还有s1[i-1]==s2[j-1]则将其加入;否则的话,它的左边或上边(根据公式)至少有一个与它相等,于是往与它相等的方向走一格;到左上角为止。这其实相当于把动态规划过程倒过来做了一遍。

    d1e3260c03fae0df69d6e385055ead17.png

    最长公共子串

    子串和子序列的区别在于,子串必须是连续的。求最长公共子串的长度和求最长公共子序列的长度的方法几乎一样,我们用dp[i][j]代表以

    的第
    i个元素、
    的第
    j个元素结尾的最长公共子串的长度。那么当s1[i-1]==s2[j-1]时递推公式与最长公共子序列的情形一致,但是当s1[i-1]!=s2[j-1] 时会直接为0。这样写的话,因为我们不知道最长公共子串是以那两个元素结尾的,所以我们就需要枚举ij来求最大值:
    while (cin >> s1 >> s2)
    {
        memset(dp, 0, sizeof(dp));
        int n1 = strlen(s1), n2 = strlen(s2), ma = 0;
        for (int i = 1; i <= n1; ++i)
            for (int j = 1; j <= n2; ++j)
                if (s1[i - 1] == s2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = 0;
        for (int i = 1; i <= n1; ++i)
            for (int j = 1; j <= n2; ++j)
                ma = max(ma, dp[i][j]);
        cout << ma << endl;
    }
    

    得到的dp二维数组如下:

    d307552550c77a0091229d5942356ed2.png

    这个要输出答案就更简单了,找到使dp[i][j]最大的ij,将对应的串从ij处开始往前数dp[i][j]个元素,得到的子串就是最长公共子串。

    变式

    (CF1446B Catching Cheaters)

    You are given two strings
    and
    representing essays of two students who are suspected cheaters. For any two strings CC, DD we define their similarity score
    as
    , where
    denotes the length of the Longest Common
    Subsequence of strings
    and
    .

    You believe that only some part of the essays could have been copied, therefore you're interested in their substrings.
    Calculate the maximal similarity score over all pairs of substrings. More formally, output maximal
    over all pairs
    , where
    is some substring of
    , and
    is some substring of
    .

    If
    is a string,
    denotes its length.

    A string
    is a
    substring of a string
    if
    can be obtained from
    by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

    A string
    is a
    subsequence of a string
    if aa can be obtained from
    by deletion of several (possibly, zero or all) characters.

    Pay attention to the difference between the substring and subsequence, as they both appear in the problem statement.
    You may wish to read the Wikipedia page about the Longest Common Subsequence problem.Input
    The first line contains two positive integers
    and
    (
    ) — lengths of the two strings
    and
    .

    The second line contains a string consisting of nn lowercase Latin letters — string
    .

    The third line contains a string consisting of mm lowercase Latin letters — string
    .
    Output
    Output maximal
    over all pairs
    , where
    is some substring of
    , and
    is some substring of
    .
    Examplesinput
    4 5
    abba
    babab output
    5input
    8 10
    bbbbabab
    bbbabaaaaa output
    12input
    7 7
    uiibwws
    qhtkxcn output
    0

    这个题其实就是最长公共子序列和最长公共子串的混合体,我们用dp[i][j]表示代表以

    的第
    i个元素、
    的第
    j个元素结尾的子串的最大
    值。于是我们考虑转移,当
    s1[i-1]==s2[j-1]时, 可以从dp[i-1][j-1]转移过来,
    值加2;当
    s1[i-1]!=s2[j-1]时,则是从dp[i-1][j]dp[i][j-1]中的最大值转移过来,
    值减1(但减到小于0时取0,因为可以不取)。
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 2;
            else
                dp[i][j] = max(max(dp[i - 1][j] - 1, dp[i][j - 1] - 1), 0);
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            ma = max(ma, dp[i][j]);
    

    Pecco:算法学习笔记(目录)zhuanlan.zhihu.com
    展开全文
  • (给算法爱好者加星标,修炼编程内功)作者:山大王wld (本文来自作者投稿)1,最长公共子串假如有两个字符串,s1="people"和s2="eplm",我们要求他俩最长的公共子串。我们一眼就能看出他们的最长公共子串是"pl",长度...

    (给算法爱好者加星标,修炼编程内功)

    作者:山大王wld (本文来自作者投稿)

    1,最长公共子串

    假如有两个字符串,s1="people"和s2="eplm",我们要求他俩最长的公共子串。我们一眼就能看出他们的最长公共子串是"pl",长度是2。但如果字符串特别长的话就不容易那么观察了。

    1,暴力求解:暴力求解对于字符串比较短的我们还可以接受,如果字符串太长实在是效率太低,所以这种我们就不再考虑

    2,动态规划:我们用一个二维数组dp[i][j]表示第一个字符串前i个字符和第二个字符串前j个字符组成的最长公共字符串的长度。那么我们在计算dp[i][j]的时候,我们首先要判断s1.charAt(i)是否等于s2.charAt(j),如果不相等,说明当前字符无法构成公共子串,所以dp[i][j]=0。如果相等,说明可以构成公共子串,我们还要加上他们前一个字符构成的最长公共子串长度,也就是dp[i-1][j-1]。所以我们很容易找到递推公式

    01最长公共子串的递推公式
    1    if(s1.charAt(i) == s2.charAr(j))2        dp[i][j] = dp[i-1][j-1] + 1;3    else4        dp[i][j] = 0;
    02最长公共子串画图分析

    1396dd586dc77f6b6dd959d00717140a.png

    我们看到在动态规划中,最大值不一定是在最后一个空格内,所以我们要使用一个临时变量在遍历的时候记录下最大值。代码如下

    03最长公共子串代码
     1public static int maxLong(String str1, String str2) {
    2    if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)
    3        return 0;
    4    int max = 0;
    5    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    6    for (int i = 1; i <= str1.length(); i++) { 7        for (int j = 1; j <= str2.length(); j++) { 8            if (str1.charAt(i - 1) == str2.charAt(j - 1)) 9                dp[i][j] = dp[i - 1][j - 1] + 1;10            else11                dp[i][j] = 0;12            max = Math.max(max, dp[i][j]);13        }14    }15    Util.printTwoIntArrays(dp);//这一行是打印测试数据的,也可以去掉16    return max;17}18

    2-3行是一些边界的判断。

    重点是在8-11行,就是我们上面提到的递推公式。

    第12行是记录最大值,因为这里最大值不一定出现在数组的最后一个位置,所以要用一个临时变量记录下来。

    第15行主要用于数据的测试打印,也可以去掉。

    我们还用上面的数据来测试一下,看一下结果

    1public static void main(String[] args{
    2    System.out.println(maxLong("eplm""people"));
    3}

    运行结果

    cb8603cb5fd33332ed6545aab7ddbd06.png

    结果和我们上面图中分析的完全一致。

    我们发现上面的代码有个规律,就是在遍历的时候只使用了dp数组的上面一行,其他的都用不到,所以我们可以考虑把二维数组转化为一位数组,来看下代码

    04最长公共子串代码优化
     1public static int maxLong(String str1, String str2{
    2    if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)
    3        return 0;
    4    int max = 0;
    5    int[] dp = new int[str2.length() + 1];
    6    for (int i = 1; i <= str1.length(); i++) {
    7        for (int j = str2.length(); j >= 1; j--) {
    8            if (str1.charAt(i - 1) == str2.charAt(j - 1))
    9                dp[j] = dp[j - 1] + 1;
    10            else
    11                dp[j] = 0;
    12            max = Math.max(max, dp[j]);
    13        }
    14        Util.printIntArrays(dp);//这一行和下面一行是打印测试数据的,也可以去掉
    15        System.out.println();
    16    }
    17    return max;
    18}

    上面第7行的for循环我们使用的倒序的方式,这是因为dp数组后面的值会依赖前面的值,而前面的值不依赖后面的值,所以后面的值先修改对前面的没影响,但前面的值修改对后面的值有影响,所以这里要使用倒序的方式。

    我们还用上面的两个字符串来测试打印一下

    952faeb9891104fc7d517229909bb65c.png

    我们看到结果和之前的完全一样。

    1bd18dce96880f45639655bfd6f11733.png

    2,最长公共子序列

    上面我们讲了最长公共子串,子串是连续的。下面我们来讲一下最长公共子序列,而子序列不是连续的。我们还来看上面的两个字符串s1="people",s2="eplm",我们可以很明显看到他们的最长公共子序列是"epl",我们先来画个图再来找一下他的递推公式。

    05最长公共子序列画图分析

    e7bb095f51d8cc66d29efe5d4de1e160.png

    我们通过上面的图分析发现,子序列不一定都是连续的,只要前面有相同的子序列,哪怕当前比较的字符不一样,那么当前字符串之前的子序列也不会为0。换句话说,如果当前字符不一样,我们只需要把第一个字符串往前退一个字符或者第二个字符串往前退一个字符然后记录最大值即可。

    举个例子,比如图中第4行第4列(就是图中灰色部分),p和m不相等,如果字符串"eplm"退一步是"epl"再和"epop"对比我们发现有2个相同的子序列(也就是上面表格中数组(2,3)位置)。如果字符串"peop"退一步是"peo"再和"eplm"对比我们发现只有1个相同的子序列(这里的pe和ep只能有一个相同,要么p相同,要么e相同,因为子序列的顺序不能变)(也就是上面表格中数组(3,2)位置)。所以我们很容易找出递推公式

    06最长公共子序列的递推公式
    1    if(s1.charAt(i) == s2.charAr(j))2        dp[i][j] = dp[i-1][j-1] + 1;3    else4        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

    有了上面的递推公式,代码就很容易写出来了,我们来看下

    07最长公共子序列代码
     1public static int maxLong(String str1, String str2) {
    2    if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)
    3        return 0;
    4    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    5    for (int i = 1; i <= str1.length(); i++) { 6        for (int j = 1; j <= str2.length(); j++) { 7            if (str1.charAt(i - 1) == str2.charAt(j - 1)) 8                dp[i][j] = dp[i - 1][j - 1] + 1; 9            else10                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);11        }12    }13    Util.printTwoIntArrays(dp);//这一行是打印测试数据的,也可以去掉14    return dp[str1.length()][str2.length()];15}16

    我们发现他和最长公共子串的唯一区别就在第10行,我们还用图中分析的两个字符串测试一下,看一下结果

    08最长公共子序列测试结果

    a7ba42d3398c012816bea81c432ce93c.png

    我们看到打印的结果和上面图中分析的完全一致。上面在讲到最长公共子串的时候我们可以把二维数组变为一维数组来实现对代码性能的优化,这里我们也可以参照上面的代码来优化一下,但这里和上面稍微有点不同,如果当前字符相同的时候,他会依赖左上角的值,但这个值有可能会被上一步计算的时候就被替换掉了,所以我们必须要先保存下来,我们来看下代码

    09最长公共子序列代码优化
     1public static int maxLong(String str1, String str2{
    2    if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)
    3        return 0;
    4    int[] dp = new int[str2.length() + 1];
    5    int last = 0;
    6    for (int i = 1; i <= str1.length(); i++) {
    7        for (int j = 1; j <= str2.length(); j++) {
    8            int temp = dp[j];//dp[j]这个值会被替换,所以替换之前要把他保存下来
    9            if (str1.charAt(i - 1) == str2.charAt(j - 1))
    10                dp[j] = last + 1;
    11            else
    12                dp[j] = Math.max(dp[j], dp[j - 1]);
    13            last = temp;
    14        }
    15        Util.printIntArrays(dp);//这一行和下面一行是打印测试数据的,也可以去掉
    16        System.out.println();
    17    }
    18    return dp[str2.length()];
    19}

    代码在第8行的时候先把要被替换的值保存下来,我们还是用上面的数据来测试一下,看一下打印结果

    10最长公共子序列优化测试结果

    cea1317f809992c2e7a71efe1463303e.png

    我们看到结果和我们之前分析的完全一致。

    推荐阅读  点击标题可跳转LCS 算法:JavaScript 最长公共子序列算法题:有效的括号序列算法题:乘积最大子序列

    觉得本文有帮助?请分享给更多人

    关注「算法爱好者」加星标,修炼编程内功

    74bcb03b267cf0b900164a26933c1044.png

    好文章,我在看❤️

    展开全文
  • 最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
  • 上面两个字符串,如果通过计算子串来求相似度,会发现相似度比较低,但如果考虑用最长公共子序列算法求相似度问题,则相似度会很高。子串是有序且连续的,而子序列是有序但不一定连续。那么,本文就来讲讲如何求两个...

    在前面我讲解了如何通过最长公共子串来求解两个文本的相似度问题,但它有一定缺陷,举个例子,看下面的两个字符串

    我爱吃小青菜和各种鲜水果。

    我很爱吃青菜与各样水果。

    上面两个字符串,如果通过计算子串来求相似度,会发现相似度比较低,但如果考虑用最长公共子序列算法求相似度问题,则相似度会很高。子串是有序且连续的,而子序列是有序但不一定连续。

    63e329cddea2fa332d2e4cc15b23f5be.png

    那么,本文就来讲讲如何求两个字符串的最长公共子序列。

    一. 暴力解法

    跟求最长公共子串一样,也可以用暴力方法来求解最长公共子序列问题,但是复杂度会更高,时间复杂度是指数级别的,很显然,这种方法行不通。

    二. 动态规划法

    假如两个字符串分别表示为X=[x_0, x_1, ..., x_m-1],Y=[y_0, y_1, ..., y_n-1],通过动态规划法求最长公共子序列,那么用dp[i][j]来表示以x_i和y_j为结尾的最长公共子串的长度,那么

    1. 当x_i=y_j时,dp[i][j] = dp[i - 1][j - 1] + 1
    2. 当x_i≠y_j时,dp[i][j]为dp[i - 1][j]和dp[i][j - 1]中最大的那个

    所以得到其状态转移方程如下

    f35bf5e0f02fbcd56d9ac194e1f37533.png

    代码如下

    int LCS(string x, string y) { int xlen = x.size(); int ylen = y.size(); for (int i = 0; i <= xlen; i++) { for (int j = 0; j <= ylen; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (x[i - 1] == y[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[xlen][ylen];}

    很明显,基于动态规划法的最长公共子序列的时间复杂度为O(mn)。

    后面会讲解更多关于求解文本相似度问题的算法,欢迎大家的关注!

    展开全文
  • 在线评测地址:LintCode 领扣说明最长公共子序列的定义:最长公共子序列问题是在一组序列(通常2个)中找到最长公共子序列(注意:不同于子串,LCS不需要是连续的子串)。该问题是典型的计算机科学问题,是文件差异...

    给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。

    在线评测地址:LintCode 领扣

    说明

    最长公共子序列的定义:

    • 最长公共子序列问题是在一组序列(通常2个)中找到最长公共子序列(注意:不同于子串,LCS不需要是连续的子串)。该问题是典型的计算机科学问题,是文件差异比较程序的基础,在生物信息学中也有所应用。
    • https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

    样例 1:

            输入:  "ABCD" and "EDCA"
            输出:  1
     
            解释:
            LCS 是 'A' 或  'D' 或 'C' 

    样例 2:

            输入: "ABCD" and "EACB"
            输出:  2
     
            解释: 
            LCS 是 "AC" 

    算法:动态规划(dp)

    算法思路

    • 设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列,将 X 和 Y 的最长公共子序列记为LCS(X,Y)
    • 找出LCS(X,Y)就是一个最优化问题。因为,我们需要找到X 和 Y中最长的那个公共子序列。而要找X 和 Y的LCS,首先考虑X的最后一个元素和Y的最后一个元素。
    1. xn = ym​,即X的最后一个元素与Y的最后一个元素相同,这说明该元素一定位于公共子序列中。因此,现在只需要找:LCS(Xn-1,Ym-1)。
    2. xn != ym​,这下要麻烦一点,因为它产生了两个子问题:LCS(Xn-1,Ym) 和 LCS(Xn,Ym-1)。因为序列 X 和 序列 Y 的最后一个元素不相等,那说明最后一个元素不可能是最长公共子序列中的元素。求解上面两个子问题,得到的公共子序列谁最长,那谁就是 LCS(X,Y)。用数学表示就是 LCS=max(LCS(Xn−1,Ym),LCS(Xn,Ym−1))LCS=max(LCS(Xn−1,Ym),LCS(Xn,Ym−1))
    我们成功地把原问题转化成了三个规模更小的子问题。 这样就可以用动态规划的方法来解决这个问题

    代码思路

    • dp[i][j]dp[i][j]表示表示A序列前i个,与B序列的前j个的LCS长度
    • 状态转移方程

    f4e0febcc9991b51d7093839d1d675f4.png

    复杂度分析

    N表示序列S的长度,M表示序列B的长度

    • 空间复杂度:O(NM)
    • 时间复杂度:O(NM)
    public 

    更多题解参考:九章算法

    展开全文
  • 利用动态规划的思想,通过设置一个临时数组t[][],其中t[i][j]表示,以Str1[i]作为末尾和以Str[2]作为末尾的最长公共子序列或者子串的长度。 算法步骤: (1)将输入的两个字符串分别存在数组a[]和b[]中,同时设置两...
  • 前言推出一个新系列,《看图...最长公共子序列最长公共子序列,英文为Longest Common Subsequence,缩写LCS。一个序列,如果是某两个或多个已知序列的最长子序列,则称为最长公共子序列。另外,要注意的是最长公共...
  • 最长公共子序列C语言

    千次阅读 2018-11-03 11:57:11
    问题: 设X有m个元素,Y有n个元素,求得X和Y的最长公共子序列。 注意:这问题如果用蛮力算法,时间复杂度是指数级别的,不太好。 考虑一下子问题之间的依赖关系(设Z是X和Y的最长公共子序列,有k个元素): 若X最后...
  • 点击蓝色“力扣加加”关注我哟加个“星标”...最长公共子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长公共子序列。那么问题来了,它穿上衣服你还看得出来是...
  • (给算法爱好者加星标,修炼编程内功)来源:码海题目:给定两个字符串 str1 和 str2,返回这两个字符串的最长公共子序列的长度解释:一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对...
  • 最长公共子序列C语言算法-动态规划:算法与数据结构参考 题目: 给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变...
  • 在两个字符串中,有些字符会一样,可以形成的子序列也有可能相等,因此,长度最长的相等子序列便是两者间的最长公共字序列,其长度可以使用动态规划来求。以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。借用...
  • 最长公共子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长公共子序列。那么问题来了,它穿上衣服你还看得出来是么?如果你完全看不出来了,说明抽象思维还不到...
  • 算法导论 动态规划 最长公共子序列 c语言实现
  • 最长公共子序列C语言

    千次阅读 2017-08-03 23:58:57
    这个系列的内容均出自《算法设计与问题求解》,有兴趣的可以去看原版书。 输出: 4C(x,y) = 0 当 i=0, j=0时 C(i-1,j-1)+1 当i,j>0,Xi=Yi时 max{C(i-1, j), C(i, j-1)} 当i,j>0, Xi!=Yj时#include #include...
  • C语言最长公共子序列问题的算法实现。LCS问题,没有太多的描述语言了,这个资源很简单的。
  • 可以根据里面代码修改具体输出,实现过程根据《算法导论》
  • 在前一课中,我们讨论了最长公共子序列(LCS)问题,并且讨论了如何计算两个序列的LCS的长度,但是没有输出具体的LCS序列。在本课中,我们讨论了如何构造和输出LCS具体序列。【问题】给定两个序列,请找出两个...
  • 最长上升子序列给定一个长度为N的数列(w[N]),求数值严格单调递增的子序列的长度最长是多少。样例输入格式 第一行包含整数N。第二行包含N个整数,表示完整序列。输出格式 输出一个整数,表示最大长度。数据范围 1 ≤...
  • 读完本文,你可以去力扣拿下如下题目:516.最长回文子序列---------...而且,子序列问题很可能涉及到两个字符串,比如前文「最长公共子序列」,如果没有一定的处理经验,真的不容易想出来。所以本文就来扒一扒子序列...
  • ①计算最长公共子序列长度的动态规划算法LscLength以数组ar,br作为输入。输出两个数组c和b。其中,c[i][j]存储ar和br的最长公共子序列的长度,b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的,这在构造最长...
  • #include #define N 7#define M 7int max(int x, int y);void LCS(int L[N + 1][M + 1], char *strA, char *strB);void disp(int a[N + 1][M + 1]);int main() { char strA[] = "xzyzzyx"; char strB[] =
  • #include #include int b[50][50];int c[50][50];int length=0;void lcs(char* x,int m,char* y,int n){ int i; int j; for (i=1;i for (i=1;i c[0][0] = 0; for (i=1;i for (j=1;j { if (x[i-1] == y[j-
  • 本课程是从少年编程网...最长的交替(Zig-Zag)子序列问题是找到给定序列的最长子序列的长度,以使该子序列中的所有元素交替出现。【定义】如果序列{x1,x2,.. xn}是交替序列,则其元素满足以下关系之一: x1<x...
  • 算法导论实验:动态规划实现最长公共子序列问题,python实现; KR算法c语言实现。 附实验报告以及相关KMP算法的调研。
  • 分析并掌握“最长公共子序列” 问题的动态规划算法求解方法; 最长公共子序列问题:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1...
  • 算法提高 最长字符序列 时间限制:1.0s 内存限制:256.0MB    最长字符序列 问题描述  设x(i), y(i), z(i)表示单个字符,则X={x(1)x(2)……x(m)},Y={y(1)y(2)……y(n)},Z={z(1)z(2)……z(k)},我们称其为...
  • 计算最长公共子序列

    千次阅读 2018-09-03 20:42:27
    前言 什么是最长公共子序列呢?好比一个数列 S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则S 称为已知...算法导论—–最长公共子序列LCS(动态规划) 我的代码 c语言 #in...

空空如也

空空如也

1 2 3
收藏数 60
精华内容 24
关键字:

最长公共子序列c语言算法

c语言 订阅