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

题目描述：给定两个字符串A、B，求出两个字符串的最长公共子串和最长公共子序列。

解析：这两个题目很容易混淆，解题思路类似，在这里一并总结。最长公共子串要求必须是连续的，而最长公共子序列则不要求连续，这是唯一的区别，都是采用动态规划的思路来求解。比如s1=”BCBDAB”,s2=”ABDCDABA”，则他们的最长功能子串是：”DAB”，而它们的最长公共子序列是：”BCDAB”。

1.最长公共子串：令dp[i][j]表示s1的以i结尾的子串和s2以j结尾的子串的最长公共子串长度。如果s1[i]==s2[j]，则dp[i][j]=dp[i-1][j-1] + 1，否则dp[i][j] = 0。代码如下：

#include <iostream>
#include <vector>
using namespace std;

int LCS(string s1, string s2)
{
    int len1 = s1.size();
    int len2 = s2.size();
    int max_len = 0;
    vector< vector<int> > dp(len1+1, vector<int>(len2+1, 0));
    for(int i=0; i <= len1; i++)
        for(int j=0; j <= len2; j++)
        {
            if(i==0 || j ==0)
                dp[i][j] = 0;
            else if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                max_len = max(max_len, dp[i][j]);
            }
            else
                dp[i][j] = 0;
        }
    cout << "max_len:" << max_len << endl;
    return max_len;
}

int main()
{
    string s1 = "ABCBDAB";
    string s2 = "BDCDABA";
    int lcs = LCS(s1, s2);
    cout << "最长公共子串长度：" << lcs << endl;
    return 0;
}

2.最长公共子序列

动态规划的定义方式与上面相同，不同在于子序列可以不要求连续，因此当s1[i]!=s2[j]，比较s1去掉当前元素i或者s2去掉当前元素j两种情况取最优的，具体代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int LCS(string s1, string s2)
{
    int len1 = s1.size();
    int len2 = s2.size();
    vector< vector<int> > dp(len1+1, vector<int>(len2+1, 0));
    for(int i=0; i <= len1; i++)
        for(int j=0; j <= len2; j++)
        {
            if(i==0 || j ==0)
                dp[i][j] = 0;
            else 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]);
        }
    return dp[len1][len2];
}

int main()
{
    string s1 = "ABCBDAB";
    string s2 = "BDCABA";
    int lcs = LCS(s1, s2);
    cout << "最长公共子序列：" << lcs << endl;
    return 0;
}