题解 | #最长公共子串#

与最长公共子序列相似，只不过修改迭代条件即可，因为子串是连续额的，所以我们可以使用两个变量就可以截取出最长公共子串：

• maxLen，记录最大公共子串长度
• lastIdx，最长公共子串的结尾位置

class Solution {
public:
    
    string LCS(string str1, string str2) {
        int n = str1.size(), m = str2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        int maxLen = 0;
        int lastIdx = -1;
        for(int i = 1; i <= n; i ++){
            for(int j = 1;j <= m;j ++){
                if(str1[i - 1] == str2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = 0;
                }
                if(maxLen < dp[i][j]){
                    maxLen = dp[i][j];
                    lastIdx = i - 1;
                }
            }
        }

        return str1.substr(lastIdx - maxLen + 1, maxLen);
    }
};