题解 | #公共子串计算#

该题主要思路是动态规划
第一步：确定动态数组及下标含义
由于是计算两个字符串之间的最长公共子串，所以考虑dp为二维数组
dp[i][j]:表示以下标i-1结尾的子串和以下标j-1结尾的子串的最长公共子序列长度为dp[i][j]
第二步：确定动态方程
如果str1[i - 1] == str2[j - 1]则dp[i][j] = dp[i - 1][j - 1] + 1,否则dp[i][j] = 0;
第三步：初始化条件
dp[0][j] =0;
dp[i][0] = 0;
最终实现代码如下：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int strLen(const string& str1, const string& str2);
int main(){
    string str1;
    string str2;
    while(cin >> str1 >> str2){
        cout << strLen(str1, str2) << endl;
    }
    return 0;
}

//动态规划实现
int strLen(const string& str1, const string& str2){
    if(str1.size() == 0 || str2.size() == 0)
        return 0;
    vector<vector<int>> dp(str1.size() + 1, vector<int>(str2.size() + 1, 0));
    int res = 0;
    for(int i = 1; i < dp.size(); ++i){
        for(int j = 1; j < dp[0].size(); ++j){
            if(str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            if(dp[i][j] > res)
                res = dp[i][j];
        }
    }
    return res;
}