LCS

最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。

最长公共子串

/*
    dp[i][j] 表示选s1第i个字符和s2第j个字符的公共子串长度
    状态转移方程：
        if s1[i-1] == s2[j-1]
            dp[i][j] = dp[i-1][j-1] + 1
        else
            dp[i][j] = 0
    最后返回max(dp[i][j])
*/
int LCSSubstring(string s1, string s2) {
    int m = s1.length(),  n = s2.length(), res = 0;
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 0; i < m; i++)
        if (s1[i] == s2[0])
            dp[i+1][1] = 1;
    for (int j = 0; j < n; j++)
        if (s1[0] == s2[j])
            dp[1][j+1] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(s1[i] == s2[j])
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = 0;
            res = max(res, dp[i+1][j+1]);
        }
    }
    return res;
}
    

最长公共子序列

/*
    dp[i][j] 表示s1前i个字符和s2前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])
        最后返回dp[m][n]
*/
int longestCommonSubsequence(string s, string t) {
    int n = s.size(), m = t.size();
    vector dp(n + 1, vector<int>(m + 1, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s[i] == t[j])
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
        }
    }
    return dp[n][m];
}