题解 | #最长公共子串#

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        int n1 = str1.size(), n2 = str2.size();
        vector<vector<int>> dp(n1,vector<int>(n2,0));
        dp[0][0] = str1[0]==str2[0]?1:0;
        if(str1==str2) return str1;
        int max_length = str1[0]==str2[0]?1:0;
        int end=0;
        for(int i=0; i<n1-1; i++){
            for(int j=0; j<n2-1; j++){
                dp[i+1][j+1] = str1[i+1]==str2[j+1]?dp[i][j]+1:0;
                max_length = (str1[i+1]==str2[j+1])&&(dp[i+1][j+1]>=max_length)?(dp[i+1][j+1]):max_length;
                end = (str1[i+1]==str2[j+1])&&(dp[i+1][j+1]>=max_length)?i+1:end;
            }
        }
        return str1.substr(end-max_length+1, max_length);;
    }
};