#公共子串计算# 解决了“未来0116”代码数组访问溢出

公共子串计算

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

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


int main() {
    string str1, str2;
    while (cin >> str1 >> str2) { // 注意 while 处理多个 case
        int str1Len = str1.length();
        int str2Len = str2.length();
        vector<vector<int>> dp(str1Len+1, vector<int>(str2Len+1, 0));
        int maxLen = 0;

        for(int j = 0; j<str2Len; ++j){
            if(str1[0] == str2[j]){
                dp[0][j] = 1;
                maxLen = max(maxLen, dp[0][j]);
            } 
        }
        for(int i = 0; i<str1Len; ++i){
            if(str1[i] == str2[0]){
                dp[i][0] = 1;
                maxLen = max(maxLen, dp[i][0]);
            } 
        }
        
        for(int i = 1; i<= str1Len; i++){
            for(int j = 1; j<= str2Len; j++){
                if(str1[i] == str2[j] && i<str1Len && j<str2Len){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = 0;
                }
                maxLen = max(maxLen, dp[i][j]);
            }
        }
        cout<< maxLen<< endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务