题解 | #最长公共子串#

dp[i][j] 表示以str1[i]结尾和以str2[j]结尾的最长子串； 要注意和最长公共子序列这道题的差异

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int m = str1.length(), n = str2.length();
        
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        int res_i;
        int res = 0;
        
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(str1[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(dp[i][j] > res){
                    res_i = i-1;
                    res = dp[i][j];
                }
            }
        }
        
        string str = str1.substr(res_i - res + 1, res);
        //string str = to_string(res_i);
        return str;
    }
};