HJ65 查找两个字符串a,b中的最长公共子串

发表于 分类于 ， 阅读次数： Waline： 本文字数： 3.2k 阅读时长 ≈ 3 分钟

描述

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

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

数据范围：字符串长度1<= length<=30

进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)

示例

输入：

abcdefghijklmnop abcsafjklmnopqrstuvw

输出：

jklmnop

思路：

方法一：暴力搜索

我们把s1设置为较短的字符串，然后截取子串在s2中查找，维护最长的即可。

时机复杂度为：O(m^3n)，因为枚举 s1 所有的子串需要O(m^2)，find 函数查找 s2 中是否含有子串需要O(mn)

空复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

/*
暴力
*/
int main(){
    string s1,s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    //把 s1 设置为较短的字符串
    if(n > m){
        swap(s1, s2);
    }
    string res = "";
    for(int i = 0; i < s1.size(); i++){
        for(int j = i; j < s1.size(); j++){
            if(s2.find(s1.substr(i, j - i + 1)) == string::npos){
                //截取子串能够在 s2 中找不到
                break;
            }else if(res.size() < j - i + 1){
                // 更新较长的子串
                res = s1.substr(i, j - i + 1);
            }
        }
    }
    cout << res << endl;
    return 0;
}

方法二：优化

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

时机复杂度为：O(m^2n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s1,s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    //把 s1 设置为较短的字符串
    if(n > m){
        swap(s1, s2);
    }
    string res = "";
    for(int i = 0; i < s1.size(); i++){
        for(int j = 0; j < s2.size(); j++){
            int len = 0;
            int x = i, y = j;
            while(x < s1.size() && y < s2.size() && s1[x] == s2[y]){
                x++;
                y++;
                len++;
            }
            if(res.size() < len){
                //更新更大的公共子串
                res = s1.substr(i, x - i);
            }
        }
    }
    cout << res << endl;
    return 0;
}

方法三：动态规划

dp[i][j] 表示在 s1 中以 第 i 个字符结尾在 s2 中以第 j 个字符结尾时的公共子串长度，

遍历两个字符串dp数组，在这个过程中比较维护最大值即可。

转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，

dp[i][j]=dp[i−1][j−1]+1，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。

时机复杂度为：O(mn)

空间复杂度：O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s1,s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    //把 s1 设置为较短的字符串
    if(n > m){
        swap(s1, s2);
    }
    vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    int max = 0, end = 0;
    for(int i = 1; i <= s1.size(); i++){
        for(int j = 1; j <= s2.size(); j++){
            if(s1[i - 1] == s2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                // 重新开始
                dp[i][j] = 0;
            }
            if(dp[i][j] > max){
                max = dp[i][j];
                end = i - 1;
            }
        }
    }
    cout << s1.substr(end - max + 1, max) << endl;
    return 0;
}