题解 | #公共子串计算#

公共子串计算

https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b

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

class Solution{

public:
    int max_substr(string &str1, string &str2){
        int N = str1.length();
        int M = str2.length();

        vector<vector<int>> dp(N+1, vector<int> (M+1, 0)); //真的基本都是要+1的
        // dp[i][j] 子串(i-1, j-1)结尾 的最大公共子串长度,最后返回其中的最大一个
        // 如果引入的两个字符不等,则以其结尾便无法构成公共子串,为0
        // 如果相等,则加一
        int max_len = 0;
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= M; j++){
                if (str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                    dp[i][j] = 0;
                }
                max_len = max(max_len, dp[i][j]);
            }
        }

        return max_len;
    }

};

int main() {

    string str1,str2;
    cin >> str1 >> str2;

    Solution res;
    cout << res.max_substr(str1, str2) << endl;

    return 0;
}

麻了,实在过于灵活

全部评论

相关推荐

我就是0offer糕手:北大不乱杀
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务