题解 | #最长公共子串#

1. 取子串的函数： str.substr(startpos, length)
2. 动态规划要注意初始化
3. 时间复杂度O(mn), 空间复杂度O(mn)

    string LCS(string str1, string str2) {
        // write code here
        int m=str1.size(), n=str2.size();
        int maxlen=0, pos=-1;
        vector<vector<int>> dp(m, vector<int>(n));
        for(int i=m-1, j=n-1; i>=0; i--){
            if(str1[i]==str2[j]) {
                dp[i][j] = 1;
                maxlen=1;
                pos=i;
            }
        }
        for(int i=m-1, j=n-1; j>=0; j--){
            if(str1[i]==str2[j]) {
                dp[i][j] = 1;
                maxlen = 1;
                pos=j;
            }
        }
        for(int i=m-2; i>=0; i--){
            for(int j=n-2; j>=0; j--){
                if (str1[i] != str2[j]) dp[i][j] = 0;
                else{
                    dp[i][j] = 1+dp[i+1][j+1];
                    if(dp[i][j] > maxlen) {
                        maxlen = dp[i][j];
                        pos=i;
                    }
                }
            }
        }
        return str1.substr(pos, maxlen);
    }