题目简述

首先给我们两个字符串，一个命名为a，一个命名为b，然后我们要做的事情就是，找到这两个字符串中的最长的一个公共子串，然后输出

这里需要注意的是，子串是要连续的一串，然而子序列是我们中间是可以有中断的

样例解释

样例输入

abcdefghijklmnop
abcsafjklmnopqrstuvw

我们观察，然后每次都是去寻找是这么一个顺序

1. a
2. ab
3. abc
4. jklm
5. jklmn
6. jklmno
7. jklmnop

这样我们就可以得到了我们最后需要的那个子串了，所以样例输出是

jklmnop

知识点： 字符串，动态规划

难度： 三星

解法

解法一：直接暴力寻找

思路分析：

其实我们就是可以直接把较短的那个字符串，每次从第一位开始，每次都是进行一个截断，穷举出来所有的情况，然后找到最长的那个，最后输出即可

C++代码实现：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
string a, b, minn = "";
// a和b是我们输入的
// minn存储的是我们最小的那个字符串

string cut(int l, int r) {
    string tmp = "";
    for (int i = l; i <= r; i++) tmp += a[i];
    return tmp;
}
// l代表的左端点，r代表的右端点，然后我们把这段的a截取出来 

void solve() {
    if (a.size() > b.size()) swap(a, b);
    // 我们让较短的那个字符串是a
    for (int i = 0; i < a.size(); i++) {
        // 这个让a的左端点从a的每一个位置开始枚举
        for (int j = i; j < a.size(); j++) {
            // 这个是枚举a字符串截取的右端点
            string tmp = cut(i, j);
            // 获取我们截取出来的字符串
            if (b.find(tmp) != string::npos) 
                if (tmp.size() > minn.size()) minn = tmp;
            // 如果b中有截取出来的这个字符串，那么我们就是会比较和我们之前
            // 保存的最长长度字符串比较，一样的不更新，因为要保证我们取到
            // 第一个最长的，然后大于的时候进行一个更新
        }
    }
    cout << minn << "\n";
    // 输出我们最小的那个字符串
}

signed main() {
    while(cin >> a >> b) {
        minn = "";
        //  因为多组输入，所以我们要进行这样一个清空的操作
        solve();
    }
    return 0;
}

时空复杂度分析：

时间复杂度： $O(n^3)O(n^\{3\})$

理由如下：因为我们有了一个双层的for循环，然后我们在最后的一层for循环里面使用了find和我们自己手写的一个截断函数，这两个操作每一个的平均时间复杂度就是$O(n)O(n)$的，所以我们就是三个$O(n)O(n)$的，最后我们得到的时间复杂度就是一个$O(n^3)O(n^\{3\})$

空间复杂度： $O(n)O(n)$

理由如下：这里我们只是输入了长度为n的两个字符串没有进行其他的操作，所以我们的空间复杂度是$O(n)O(n)$的

解法二：动态规划

思路分析：

其实这个就是一个经典的DP问题，那我们最简单的思路其实就是我们可以开一个二维数组，那么我们这个二维数组是什么呢？假设我们定义了一个二维数组$dp[i][j]dp[i][j]$，是什么意思呢？就是代表我们a字符串的前i个字符和b的前j的字符是一样的，那么我们就要开始思考怎么想这个问题，我们现在假设

a = "abcbced";
b = "acbcbce";

这个最简单的就是画一个表格如下：

然后相同的地方设置为1，不同的地方设置为0，然后我们最后就是找最长的连续的对角线的长度就是最长的公共子串了

然后我们的状态转移方程就是：

$a[i]=b[j]:dp[i][j]=dp[i-1][j-1]+1a[i]\; =\; b[j]:\; dp[i][j]\; =\; dp[i\; -\; 1][j\; -\; 1]\; +\; 1$ $a[i]\mathrm{\ne }b[j]:dp[i][j]=0a[i]\; \backslash neq\; b[j]:\; dp[i][j]\; =\; 0$

C++代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 310;
string a, b;
int dp[N][N], maxx = 0, res = 0;
// dp就是我们的那个表格，maxx是我们的最长的地方，res是我们的a字符串的尾

void solve() {
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == b[0]) dp[i][0] = 1, maxx = 1, res = i;
        else dp[i][0] = 0;
    }
    for (int i = 0; i < b.size(); i++) {
        if (a[0] == b[i]) dp[0][i] = 1, maxx = 1, res = 0;
        else dp[0][i] = 0;
    }
    // 把我们的竖着的第一列和横着的第一行先给初始化
    for (int i = 1; i < a.size(); i++) {
        for (int j = 1; j < b.size(); j++) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                // 这个就是我们的dp转移方程
                if (dp[i][j] > maxx) maxx = dp[i][j], res = i;
                // 进行一个更新
            }
            else dp[i][j] = 0;
            // 转移方程
        }
    }
    cout << a.substr(res - maxx + 1, maxx) << "\n";
    // 我们知道了最长是多少，我们也知道了结尾是什么，我们就可以直接把这一段截取出来
}

signed main() {
    while(cin >> a >> b) {
        if (a.size() > b.size()) swap(a, b);
        // 因为要找的是短串所以我们就是要先把小的变成a
        solve();
    }
    return 0;
}

时空复杂度分析：

时间复杂度： $O(n\ast m)O(n\; *\; m)$

理由如下：我们最大的算法时间瓶颈就是在于我们的那个遍历双层for循环找到最长的对角线

空间复杂度： $O(n\ast m)O(n\; *\; m)$

理由如下：因为我们要开一个存储这两个字符串的表格，所以我们最大的空间开在这里了，所以是$O(n\ast m)O(n\; *\; m)$