《华为机试》——查找两个字符串a,b中的最长公共子串

本期给大家带来的是 华为机试题库  关于 查找两个字符串a,b中的最长公共子串 的讲解。首先，我们还是先从题目入手进行分析思考！！！

题目如下 ：👇

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

💨注：

• 子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

示例1

输入：abcdefghijklmnop
     abcsafjklmnopqrstuvw
输出：jklmnop

先给大家区分一下 “子串” 和 “子序列”  这二者的差别：

公共子串：

• 即两个字符串中相等且连续的子串序列。
• 例如：串 “abcdef” 和串 “abfcdef” 中公共子串有 【ab 】和 【cdef 】两个。

最长公共子串：

• 即在上述“公共子串”的定义中加上最长二字， 上面例子中【cdef】便是最长公共子串。

思想：

• 这个题既然提到的寻找最长公共子串，这就涉及到了 寻求最优解的问题，寻求最优解常常就会用到 动态规划算法的思想!！！！

🔥  过程图解

• 第一步:

• 第二步：

• 第三步：

• 一直这样的去计算，直到最后：

💨 解题思路：

1、【substr 】函数将两个字符串 str1 和 str2  作为输入，并返回它们之间最长的公共子字符串。

2、 它初始化大小为 （len1+1） x （len2+1） 的 二维数组 ，开始时并初始化全部元素为 0 ，其中 len1 和 len2 分别是 str1  和 str2  的长度。MSC[i][j] 的值表示以 str1  [i-1] 和 str2 [j-1] 结尾的最长公共子字符串的长度。

3、 然后，该函数循环访问 二维数组并使用以下规则填充它：

• 如果 str1[i-1] 和 str2[j-1] 相等，则 MSC[i][j] 设置为 MSC[i-1][j-1] + 1；
• 如果 str1[i-1] 和 str2[j-1] 不相等，则 MSC[i][j] 还是保持为 0。

4、 在填充 MSC 数组时，该函数还会跟踪到目前为止看到的公共子字符串的最大长度以及它结束的索引。最后，它通过将 str1 从【str1.substr(start, max_size)】 来返回最长的公共子字符串。

⌨️  代码展示

#include <iostream>
#include<string>
#include<vector>
using namespace std;
string Findmax(string& str1, string& str2) {
    //找最短的字符串
    if (str1.size() > str2.size())
        swap(str1, str2);
    //
    int len1 = str1.size();
    int len2 = str2.size();
    int start = 0;
    int max_size = 0;
    //初始化 行为 len1+1，列为len2+1 的数组元素全为0
    vector<vector<int>>MSC(len1 + 1, vector<int>(len2 + 1, 0));
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (str2[j - 1] == str1[i - 1])
                MSC[i][j] = MSC[i - 1][j - 1] + 1;
            if (MSC[i][j] > max_size)
                {
                    max_size= MSC[i][j];
                    start = i - max_size;
                }
        }
    }
    return str1.substr(start, max_size);
}
int main() {
    string str1;
    string str2;
    while (cin >> str1 >> str2) {
        string substr = Findmax(str1, str2);
        cout << substr << endl;
    }
    return 0;
}

到此，便是关于本题的详细讲解了！！