动态规划-最长公共子串

思路

一看到两个字符串的“最值”问题，一般想到二维dp。很自然地想到把str1前i个字符和str2前j个字符最长公共子串的长度作为dp[i][j]，但由于子串定义必须是原字符串连续的序列，这样定义无法找到递推关系，因此需要加限定条件——以str1[i-1]和str2[j-1]结尾的最长公共子串长度。
另外如果找不到这样的子串，应该return "-1"而不是返回空串

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.size();
        int n = str2.size();
        // dp[i][j] str1前i个字符和str2前j个字符（以其为尾字符）的最长公共子串长度
        int dp[m+1][n+1];
        int maxlen = 0, end = 0;
        //base case
        for(int i = 0; i <= m; ++i) dp[i][0] = 0;
        for(int j = 0; j <= n; ++j) dp[0][j] = 0;
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = 0;
                if(dp[i][j] > maxlen) {
                    maxlen = dp[i][j];
                    end = j - 1;
                }
            }
        }
        string r;
        if(res == 0) return "-1";
        else r = str2.substr(end-maxlen+1, res);
        return r;
    }
};