题解 | #最长公共子串#

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 max = 0, index = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(str1[i] == str2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                    if(max < dp[i+1][j+1]){
                        max = dp[i+1][j+1];
                        index = i;
                    }
                }
            }
        }
        return max == 0?"":str1.substr(index-max+1, max);
    }
};