题解 | #查找两个字符串a,b中的最长公共子串#

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

http://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506

动态规划,以第i和j个字符结尾的公共子串若存在则长度为dp[i][j],若str1[i]==str2[j]则dp[i][j]=dp[i-1][j-1]+1。求出最长并输出就行了,这个动态规划还可以压缩
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    string str1,str2;
    while(cin>>str1>>str2){
        int m = str1.size();
        int n = str2.size();
        if(m>n){
        swap(str1, str2);
        m = str1.size();
        n = str2.size();
        }
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i =0;i<m;i++){
            if(str1[i]==str2[0]) dp[i][0]=1;
        }
        for(int j =0;j<n;j++){
            if(str1[0]==str2[j]) dp[0][j]=1;
        }
        int maxlen = -1,end = 0;
        for(int i = 1;i<m;i++){
            
            for(int j = 1;j<n;j++){
                if(str1[i]==str2[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                if(dp[i][j]>maxlen) {
                    maxlen=dp[i][j];
                    end = i;
                }
            }
        }
        
        string out = str1.substr(end-maxlen+1,maxlen);
        cout<<out<<endl;
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
找工作时遇到的神仙HR
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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