题解 | #最长公共子串#

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 n = str1.size(), m = str2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        int res = 0, pos = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = 0;
                }
                if (f[i][j] > res) {
                    res = f[i][j];
                    pos = i - 1;
                }
            }
        }
        return str1.substr(pos - res + 1, res);
    }
};

• 思路：动态规划
• 状态表示：f(i, j)表示 str1以第i个字符结尾的子串 和 str2的第j个字符结尾的子串 二者的最长公共子串长度
• 状态表示：
• 1、str1[i]==str2[j]，f(i, j) = f(i - 1, j - 1) + 1
• 2、str1[i] != str2[j]，f(i, j) = 0
• 另外使用两个变量res和pos维护最长公共子串长度和最长公共子串结束位置
• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)