描述

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

数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 O(n^2)O(n2)，时间复杂度 O(n^2)O(n2)

示例1

输入： 
"1AB2345CD","12345EF"
复制
返回值： 
"2345"
复制

备注： 

1 \leq |str_1|, |str_2| \leq 5\,0001≤∣str1∣,∣str2∣≤5000

解题思路
按之前求最长公共子串长度的方法，先把长度求出来，然后使用res = str1.substr(index-cnt, cnt);来截取 
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();
        int m = str2.size();
        int cnt = 0;
        string res = "";
        int index = 0;
        // dp[i][j]代表s1的包含第i个元素与s2的包含第j个元素的最长公共子串最大长度
        vector<vector<int>>dp(n+1, vector<int>(m+1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1[i-1] == str2[j-1]) {
                    if(dp[i-1][j-1] > 0) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    } else {
                        dp[i][j] = 1;
                    }
                }
                //cout << "i=" <<i <<", j=" << j << ",dp ="<< dp[i][j] << endl;
                if (cnt < dp[i][j]) {
                    cnt = dp[i][j];
                    index = i;
                }
            }
        }
        cout << cnt;
        res = str1.substr(index-cnt, cnt);
        return res;
    }
};