题目的主要信息：

• 查找两个字符串a,b中的最长公共子串
• 若有多个，输出在较短串中最先出现的那个
• 进阶要求：时间复杂度：$O(n^3)O(n^3)$，空间复杂度：$O(n)O(n)$

方法一：暴力枚举

具体做法：

我们可以先比较两个字符串的长度，然后将s1设置为较短的字符串，s2设置为较长的字符串。

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

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        if(s1.length() > s2.length()) //使较小的字符串在前
            swap(s1, s2);
        string output = "";
        for(int i = 0; i < s1.length(); i++){ //遍历s1每个起始点的每个长度
            for(int j = i; j < s1.length(); j++){
                if(int(s2.find(s1.substr(i, j - i + 1))) < 0) //截取子串能够在s2中被找到
                    break;
                else if(output.length() < j - i + 1) //更新较长的子串
                    output = s1.substr(i, j - i + 1);
            }
        }
        cout << output << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(m^{3}n)O(m^3n)$，其中$mm$是较短字符串的长度，$nn$是较长字符串的长度，枚举s1所有的子串需要$O(m^2)O(m^2)$，find函数查找s2中是否含有子串需要$O(mn)O(mn)$
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：枚举改进

具体做法：

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

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        if(s1.length() > s2.length()) //使较小的字符串在前
            swap(s1, s2);
        string output = "";
        for(int i = 0; i < s1.length(); i++){ //遍历s1每个起始点
            for(int j = 0; j < s2.length(); j++){ //遍历s2每个起点
                int length = 0;
                int x = i, y = j;
                while(x < s1.length() && y < s2.length() && s1[x] == s2[y]){ //比较每个起点为始的子串
                    x++;
                    y++;
                    length++;
                }
                if(output.length() < length) //更新更大的长度子串
                    output = s1.substr(i, x - i);
            }
        }
        cout << output << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(m^{2}n)O(m^2n)$，其中$mm$是较短字符串的长度，$nn$是较长字符串的长度，分别枚举两个字符串每个字符作为起点，后续检查子串长度最坏需要花费$O(m)O(m)$
• 空间复杂度：$O(1)O(1)$，无额外空间

方法三：动态规划

具体做法：

动态规划继承自方法二，我们可以用$dp[i][j]dp[i][j]$表示在s1中以第$ii$个字符结尾在s2中以第$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]$后，我们维护最大值即可找到最长子串。

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        if(s1.length() > s2.length()) //使较小的字符串在前
            swap(s1, s2);
        vector<vector<int> > dp(s1.length() + 1, vector<int>(s2.length() + 1, 0)); //dp[i][j]表示到s1第i个个到s2第j个为止的公共子串长度
        int max = 0, end = 0;
        for(int i = 1; i <= s1.length(); i++){
            for(int j = 1; j <= s2.length(); j++){
                if(s1[i - 1] == s2[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];
                    end = i - 1;
                }
            }
        }
        cout << s1.substr(end - max + 1, max) << endl; //输出最长子串
    }
    return 0;
}

复杂度分析：

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