描述

给定两个字符串 $str1$ 和 $str2$, 输出两个字符串的最长公共子串。题目保证 $str1$ 和 $str2$ 的最长公共子串存在且唯一。

数据范围：
$1≤ |str1|,|str2|≤5000$

要求：
空间复杂度 $O(n^2)$，时间复杂度 $O(n^2)$

示例1

输入：

"1AB2345CD","12345EF"

返回值：

"2345"

备注：

$1 \leq |str_1|, |str_2| \leq 5000$

题解

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