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

最长公共子串

给定两个字符串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])作为新值，即它一直保存着前面已比较序列的最长公共序列值。