题解 | #最长公共子串#

/*
dp(i.j)表示，公共子串如果是最后(i,j)的话，最长子串长短是多少？
维护一个maxLen，不断更新最长子串长度。并不断记录startIndex
if(str1(i) != str2(j)) {
    dp(i,j) = 0
} else {
    dp(i,j) = dp(i-1,j-1) + 1;
    if(maxLen < dp(i,j)) {
        maxLen = dp(i,j);
        startIndex = i - maxLen;
    }
}
这里要注意的是，dp(ij)的含义，不是截止i，j最大的长度，而是以i，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 len1 = str1.length(), len2 = str2.length();
        int startIndex = 0, maxLen = 0;
        vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1[i-1] != str2[j-1]) {
                    continue;
                }
                dp[i][j] = dp[i-1][j-1] + 1;
                if(maxLen < dp[i][j]) {
                    maxLen = dp[i][j];
                    startIndex = i - maxLen;
                }
            }
        }
        
        return str1.substr(startIndex, maxLen);
            
    }
};