美文网首页
C语言实现最长公共子串与最长公共子序列

C语言实现最长公共子串与最长公共子序列

作者: JerryShieh | 来源:发表于2020-08-04 17:34 被阅读0次

最长公共子串

给定两个字符串s1="GeeksforGeeks",s2="GeeksQuizGo",则它们的最长公共子串为“Geeks”,长度为5。

算法

运用动态规划的思想,将两个字符串映射为一张二维表,表格中的值代表到当前为止的最长公共子串的值,如下图所示:


Longest Common Substring.png

生成这张表的步骤(假设这张表为t[][], r为行标,c为列标):

  1. 表的第一行与第一列都置为0。
  2. 如果s1[r] == s2[c],则当前表格的值 t[r][c] 为 t[r-1][c-1] + 1,即为左上角的值加1。
  3. 若是s1[r] != s2[c],则 t[r][c]重新置为0。
  4. 整张表生成完后,表格中的最大值即为最长公共子串的长度。

Code

int lcs(const char* str1, const char* str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    char dp[1000][1000];    // dp array for recording the all comparative information of these two strings.
    int rowIndex;
    int columnIndex;
    int maxLen = 0;         // record the maximum length of substring.
    int maxRow = 0;         // record the row num of the maxLen in dp array.

    // Init the first column with 0
    for (rowIndex = 0; rowIndex < len1 + 1; rowIndex++)
    {
        dp[rowIndex][0] = 0;
    }

    // Init the first row with 0
    for (columnIndex = 0; columnIndex < len2 + 1; columnIndex++)
    {
        dp[0][columnIndex] = 0;
    }

    for (rowIndex = 1; rowIndex < len1 + 1; rowIndex++)
    {
        for (columnIndex = 1; columnIndex < len2 + 1; columnIndex++)
        {
            if (str1[rowIndex - 1] == str2[columnIndex - 1])        // because the begin of rowIndex and columnIndex are 1, so they both need to minus 1.
            {
                dp[rowIndex][columnIndex] = dp[rowIndex - 1][columnIndex - 1] + 1;  // Its value depends on diagonal.
            }
            else
            {
                dp[rowIndex][columnIndex] = 0;
            }

            if (maxLen < dp[rowIndex][columnIndex])
            {
                maxLen = dp[rowIndex][columnIndex];
                maxRow = rowIndex;
            }
        }
    }

    // Print the Longest Common Substring
    // char s[100];
    // int i = 0;
    // for (int j = maxRow - maxLen; i < maxLen; i++, j++)
    // {
    //     s[i] = str1[j];
    // }
    // s[i] = '\0';
    // printf("The Longest Common Substring is %s\n", s);

    return maxLen;

}

整个算法的时间复杂度为O(len1 * len2),len1与len2分别为两个字符串的长度。


最长公共子序列

最长公共子序列与最长公共子串的区别是,最长公共子序列不要求“连续匹配”,它的目的是找到两个字符串中最大的公共部分。依然以s1="GeeksforGeeks",s2="GeeksQuizGo"为例,它们的最长公共子序列为“Geekso”和“GeeksG”,长度为6。

算法

它的二维表如下所示:


Longest Common Subsequence.png

它的生成步骤与最长公共子序列的最大不同在第3步,最长公共子序列在遇到s1[r] != s2[c]情况时,不会将t[r][c]重置为0,而是选择Max(t[r-1][c], t[r][c-1])作为新值,即它一直保存着前面已比较序列的最长公共序列值。

相关文章

  • 最长公共子序列和最长公共子串

    最长公共子序列和最长公共子串区别 最长公共子串(Longest CommonSubstring)和最长公共子序列(...

  • LCS问题

    LCS问题包括最长公共子序列和最长公共子串,其中,最长公共子串要求必须连续。 对于二者的求解方式 最长公共子序列:...

  • 子串 子序列 总结

    最长公共子串 子串的要求比子序列严格,所以可以讨论子串的终点 最长公共子序列 DP解 递归+memo 最长公共回文...

  • 两个字符串的最长公共子串

    最长公共子串(Longest Common Substring)与最长公共子序列(Longest Common S...

  • 算法(04)动态规划

    零钱问题 背包问题 最长公共子序列 最长公共子串 最长上升子序列 最大连续子序列和

  • 字符串算法

    最长公共前缀 最长回文串 最长回文子序列 最长公共子串 反转单词顺序列 反转字符串 字符串转数字 IP-int互转

  • 公共子序列问题

    最长公共子序列 最长上升子序列 最长公共上升子序列

  • 每天一道算法题18

    【最长公共子序列,子串】给定两个字符串上str1 和 str2, 求两个字符的最长公共子序列和最长公共子串。 最长...

  • 字符串的几个问题

    1.最长公共子序列2.最长公共子串3.最长回文串4.最长回文序列5.最长递增序列6.最长先增后减序列7.(最短)编...

  • 动态规划 最长公共子串

    核心思路和最长公共子序列一样 区别在于子串必须连续 可以先看我之前这篇文章最长公共子序列问题总结 最长公共子串同样...

网友评论

      本文标题:C语言实现最长公共子串与最长公共子序列

      本文链接:https://www.haomeiwen.com/subject/zuewrktx.html