前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最长公共子串 动态规划_最长公共子串 DNA序列

最长公共子串 动态规划_最长公共子串 DNA序列

作者头像
全栈程序员站长
发布2022-09-21 21:04:06
4410
发布2022-09-21 21:04:06
举报

大家好,又见面了,我是你们的朋友全栈君。

原题链接

题目描述 给定两个字符串str1和str2,输出连个字符串的最长公共子序列。如过最长公共子序列为空,则输出-1。 输入描述: 输出包括两行,第一行代表字符串str1,第二行代表str2。( 1<= length(str1),length(str2)<= 5000) 输出描述: 输出一行,代表他们最长公共子序列。如果公共子序列的长度为空,则输出-1。 示例1 输入

代码语言:javascript
复制
1A2C3D4B56
B1D23CA45B6A

输出

代码语言:javascript
复制
123456

说明 “123456”和“12C4B6”都是最长公共子序列,任意输出一个。 备注:

时间复杂度O(nm)O(n∗m),空间复杂度O(nm)O(n∗m)。(n,m分别表示两个字符串长度)

代码语言:javascript
复制
#include<bits/stdc++.h>
#define x first
#define y second
#define send string::nops
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
int f[N][N],path[N][N];//path用来记录dp路径
int main(){ 
   
    string str1,str2;
    cin>>str1>>str2;
    int n = str1.size(),m = str2.size();
    str1.insert(0,1,' ');
    str2.insert(0,1,' ');
// cout<<str1<<endl;
    for(int i = 1;i < str1.size();i ++){ 
   
        for(int j = 1;j < str2.size();j ++){ 
   
            if(str1[i] == str2[j])f[i][j] = f[i - 1][j - 1] + 1,path[i][j] = m * (i - 1) + j - 1;
            else { 
   
                f[i][j] = max(f[i - 1][j],f[i][j - 1]);
                if(f[i - 1][j] > f[i][j - 1])path[i][j] = m * (i - 1) + j;
                else path[i][j] = m * i + j - 1;
            }
        }
    }
    int a = str1.size() - 1,b = str2.size() - 1;
    vector<char>res;
    while(a > 0 && b > 0){ 
   
// cout<<a <<"--"<<b<<endl;
// cout<<f[a][b]<<endl;
// cout<<f[a - 1][b - 1]<<endl;
// cout<<f[a - 1][b]<<endl;
// cout<<f[a][b - 1]<<endl;
        int tt = path[a][b];
        int x = tt / m,y = tt % m;
// cout<<x<<"--"<<y<<endl;
        if(x == a - 1 && y == b - 1 && !(x == 0 && y == 0))res.push_back(str1[a]);
        a = x,b = y;
    }
    reverse(res.begin(),res.end());
    if(res.size() == 0){ 
   
        cout<<-1<<endl;
        return 0;
    }
    for(int i = 0;i < res.size();i ++)cout<<res[i];
    return 0;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/168791.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档