题解 | #公共子串计算#

HJ75公共子串计算

一.题目描述

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。

注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。

二.算法一(暴力)

由于是字串是个连续的字符串，我们可以暴力循环的方法查找截取出长串的所有字串，判断其是否会在短串中出现，下面是完整代码：

#include <bits/stdc++.h>
using namespace std;
string a,b;
int main(){
    cin>>a>>b;
    //使得a串为长串
    if(a.size()<b.size()){
        swap(a,b);
    }
    for(int i=b.size();i>=0;i--){
        for(int j=0;j<b.size()-i+1;j++){
            //利用两次循环截取出短串所有的字串
            string now=b.substr(j,i);
            if(a.find(now)!=a.npos){
                //公共串的是从大到小进行截取的 所以找到直接输出 结束
                cout<<i<<endl;
                return 0;
            }
        }
    }
    return 0;
}

时间复杂度：$O(n^3)O(n^\{3\})$，for两重循环加上每一次循环还要判断子串在不在长串中，所以复杂度达到了$O(n^3)O(n^\{3\})$。

空间复杂度：$O(1)O(1)$，不需要什么额外的空间

三.算法二(动态规划)

前一种算法很显然时间上不是很优秀，我们可以换一种思维，使用动态规划的思路去解决，很显然这是很基本的最大公共字串问题。

根据上述表格我们可以得到状态转移方程：

dp[i][j]表示以a[i],b[j]为最后一个元素的最长公共子串
当i=0或者j=0时候，dp[i][j]=0
当a[i]=b[j],dp[i][j]=dp[i-1][j-1]+1
当a[i]!=b[j],dp[i][j]=0

知道了状态转移方程我们就可以写出代码:

#include<bits/stdc++.h>
using namespace std;
const int N=155;
int dp[N][N];
//dp[i][j]表示以a[i],b[j]为最后一个元素的最长公共子串
string a,b;
int main(){
    cin>>a>>b;
    int n=a.size();
    int m=b.size();
    int mx=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            } else {
                dp[i][j]=0;
            }
            mx=max(mx,dp[i][j]);
        }
    }
    cout<<mx<<endl;
    return 0;
}

时间复杂度：$O(n^2)O(n^\{2\})$，for两重循环循进行状态转移。

空间复杂度：$O(n^2)O(n^\{2\})$，需要二维数组去记录状态转移方程。