题目的主要信息：

• 查找两个字符串a,b中的最长公共子串的长度
• 字符串只包含小写字母
• 进阶要求：时间复杂度：$O(n^3)O(n^3)$，空间复杂度：$O(n)O(n)$

方法一：暴力枚举

具体做法：

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

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

int main(){
    string s1, s2;
    while(cin >> 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.length() << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(m^{3}n)O(m^3n)$，其中$mm$是s1的长度，$nn$是s2的长度，枚举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){
        int length = 0;
        for(int i = 0; i < s1.length(); i++){ //遍历s1每个起始点
            for(int j = 0; j < s2.length(); j++){ //遍历s2每个起点
                int temp = 0;
                int x = i, y = j;
                while(x < s1.length() && y < s2.length() && s1[x] == s2[y]){ //比较每个起点为始的子串
                    x++;
                    y++;
                    temp++;
                }
                if(length < temp) //更新更大的长度子串
                    length = temp;
            }
        }
        cout << length << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(m^{2}n)O(m^2n)$，其中$mm$是s1的长度，$nn$是s2的长度，分别枚举两个字符串每个字符作为起点，后续检查子串长度最坏需要花费$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){
        vector<vector<int> > dp(s1.length() + 1, vector<int>(s2.length() + 1, 0)); //dp[i][j]表示到s1第i个个到s2第j个为止的公共子串长度
        int max = 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];
                }
            }
        }
        cout << max << endl; //输出最长子串
    }
    return 0;
}

复杂度分析：

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