题解 | #最长公共子串#

#include <vector>
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.length(), n2 = str2.length();
        int maxl = 0, maxstart = 0;
        vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxl) {
                        maxstart = i - dp[i][j];
                        maxl = dp[i][j];
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return str1.substr(maxstart, maxl);
    }
};

思路：在求最长公共子串长度的基础上，记录一个最大长度。如果最大长度发生了更新，则更新对应长度以及此时的起始位置。

最后通过起始位置与长度，用substr方法找到最长字串。