题解 | #最长公共子串#

class Solution {
public:
    string LCS(string str1, string str2) {
        string res = "";
        int len1 = str1.size(), len2 = str2.size();
        // dp[i][j]： 以 i为结尾的字符串 str1和以 j为结尾的字符串 str2的最长公共子串的长度
        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
        int finish = 0;
        int maxLen = 0;

        for(int i=1; i<=len1; i++) {
            for(int j=1; j<=len2; j++) {
                // 如果str1[i-1] == str2[j-1]，dp[i][j]=dp[i-1][j-1]+1; 否则 dp[i][j]=0
                if(str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else {
                    dp[i][j] = 0;
                }
                // 更新保存最大长度和公共字符串末尾字符的索引
                if(dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    finish = i-1;
                }
            }
        }
        return str1.substr(finish-maxLen+1, maxLen);
    }
};