题解 | #最长公共子串#（记录一下最大长度时字符串的下标）

class Solution {
public:
/**
dp[i][j]:下标i，j为结尾两字符串公共子串最大长度,且默认为0。
更新dp值只能从dp[i-1][j-1]中得到。
当str1[i] == str2[j] 
     dp[i][j] = dp[i-1][j-1] + 1
dp初始化为0；

字符串数组从0开始，dp[i-1][j-1]不存在，都错一位存储。 
*/
    string LCS(string str1, string str2) {
        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 + 1;
                    }
                }
            }
        }
        return max == 0?"-1":str1.substr(index-max, max);
    }
};