最長公共子串

給定兩個字符串s1="GeeksforGeeks"拢锹，s2="GeeksQuizGo"，則它們的最長公共子串為“Geeks”妒穴，長度為5览祖。

算法

運(yùn)用動態(tài)規(guī)劃的思想巡扇，將兩個字符串映射為一張二維表，表格中的值代表到當(dāng)前為止的最長公共子串的值垮衷，如下圖所示：

Longest Common Substring.png

生成這張表的步驟（假設(shè)這張表為t[][], r為行標(biāo)厅翔，c為列標(biāo)）：

1. 表的第一行與第一列都置為0。
2. 如果s1[r] == s2[c]搀突，則當(dāng)前表格的值 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;

}

整個算法的時間復(fù)雜度為O(len1 * len2)筒扒，len1與len2分別為兩個字符串的長度。

最長公共子序列

最長公共子序列與最長公共子串的區(qū)別是绊寻，最長公共子序列不要求“連續(xù)匹配”花墩，它的目的是找到兩個字符串中最大的公共部分。依然以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])作為新值仇箱，即它一直保存著前面已比較序列的最長公共序列值。