题目的主要信息：

• 查找两个字符串str1，str2中的最长的公共子串
• 保证str1和str2的最长公共子串存在且唯一
• 进阶要求：时间复杂度：$O(n^2)O(n^2)$，空间复杂度：$O(n^2)O(n^2)$

方法一：暴力枚举

具体做法：

遍历str1每个字符作为起点，然后遍历以其为起点的每个长度的长度，即暴力枚举字符串str1的所有子串，用find函数查看每个子串是否在字符串str2中出现，如果出现比较长更新为较长的子串长度。

class Solution {
public:
    string LCS(string str1, string str2) {
        string res = "";
        for(int i = 0; i < str1.length(); i++){ //遍历sre1每个起始点的每个长度
            for(int j = i; j < str1.length(); j++){
                if(int(str2.find(str1.substr(i, j - i + 1))) < 0) //截取子串能够在str2中被找到
                    break;
                else if(res.length() < j - i + 1) //更新较长的子串
                    res = str1.substr(i, j - i + 1);
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(m^{3}n)O(m^3n)$，其中$mm$是str1的长度，$nn$是str2的长度，枚举str1所有的子串需要$O(m^2)O(m^2)$，find函数查找str2中是否含有子串需要$O(mn)O(mn)$
• 空间复杂度：$O(1)O(1)$，res属于返回必要空间

方法二：枚举改进

具体做法：

其实找子串不用像方法一一样完全枚举，我们完全可以遍历两个字符串的所有字符串作为起始，然后同时开始检查字符是否相等，相等则不断后移，增加子串长度，如果不等说明以这两个为起点的子串截止了，不会再有了，后续比较长度维护最大值即可。

class Solution {
public:
    string LCS(string str1, string str2) {
        int length = 0;
        string res = ""; 
        for(int i = 0; i < str1.length(); i++){ //遍历s1每个起始点
            for(int j = 0; j < str2.length(); j++){ //遍历s2每个起点
                int temp = 0;
                string temps = "";
                int x = i, y = j;
                while(x < str1.length() && y < str2.length() && str1[x] == str2[y]){ //比较每个起点为始的子串
                    temps += str1[x];
                    x++;
                    y++;
                    temp++;
                }
                if(length < temp){ //更新更大的长度子串
                    length = temp;
                    res = temps;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(m^{2}n)O(m^2n)$，其中$mm$是str1的长度，$nn$是str2的长度，分别枚举两个字符串每个字符作为起点，后续检查子串长度最坏需要花费$O(m)O(m)$
• 空间复杂度：$O(n)O(n)$，res属于返回必要空间，temps属于临时空间，最坏情况下长度为$nn$

方法三：动态规划

具体做法：

动态规划继承自方法二，我们可以用$dp[i][j]dp[i][j]$表示在str1中以第$ii$个字符结尾在str2中以第$jj$个字符结尾时的公共子串长度，遍历两个字符串填充dp数组，在这个过程中比较维护最大值即可。

转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，$dp[i][j]=dp[i-1][j-1]+1dp[i][j]\; =\; dp[i\; -\; 1][j\; -\; 1]\; +\; 1$，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。

每次更新$dp[i][j]dp[i][j]$后，我们维护最大值,并更新该子串结束位置，最后根据最大值结束位置即可截取出子串。

class Solution {
public:
    string LCS(string str1, string str2) {
        vector<vector<int> > dp(str1.length() + 1, vector<int>(str2.length() + 1, 0)); //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度
        int max = 0;
        int pos = 0;
        for(int i = 1; i <= str1.length(); i++){
            for(int j = 1; j <= str2.length(); j++){
                if(str1[i - 1] == str2[j - 1]){ //如果该两位相同
                    dp[i][j] = dp[i - 1][j - 1] + 1; //则增加长度
                }
                else{ //否则
                    dp[i][j] = 0; //该位置为0
                }
                if(dp[i][j] > max){ //更新最大长度
                    max = dp[i][j];
                    pos = i - 1;
                }
            }
        }
        return str1.substr(pos - max + 1, max);
    }
};

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$是str1的长度，$nn$是str2的长度，遍历两个字符串所有字符
• 空间复杂度：$O(mn)O(mn)$，dp数组大小为$m\ast nm*n$