洛谷-最长公共子串「建议收藏」

洛谷-最长公共子串「建议收藏」原题链接题目描述给定两个字符串str1和str2,输出连个字符串的最长公共子序列。如过最长公共子序列为空,则输出-1。输入描述:输出包括两行,第一行代表字符串str1,第二行代表str2。( 1<= length(str1),length(str2)<= 5000)输出描述:输出一行,代表他们最长公共子序列。如果公共子序列的长度为空,则输出-1。示例1输入1A2C3D4B56B1D23CA45B6A输出123456说明”123456″和“12C4B6”都是最长公共

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

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

1A2C3D4B56
B1D23CA45B6A

输出

123456

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

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

#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;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168950.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • webgame开发入门[通俗易懂]

    webgame开发入门[通俗易懂]一、简单的程序框架。webgame程序构成:三大部分。第一是数据流程。第二是程序。第三是美术。其中,数据流程包括了功能。也只有在功能中才能体现数据流程。数据流程相当的麻烦,后面再讨论。比如最简单的卖买产品。要实现这个功能。那么需要有产品基础表、产品详细表、商店表、背包表。如果扩展性更强,相应的双表是少不不了的。表的问题都简单了。关键是这个物品有什么用。这样物品的来源,一大堆数据,物品的走向,又是一…

  • java模拟器.apk_java游戏模拟器安卓版下载-java模拟器apk下载 v2.2.0 安卓版-IT猫扑网…

    java模拟器.apk_java游戏模拟器安卓版下载-java模拟器apk下载 v2.2.0 安卓版-IT猫扑网…手机游戏,给用户带来无限乐趣。该应用体积小,不占用太多内存,有需要的用户赶紧下载使用吧~应用介绍:Java手机游戏模拟器主要针对诺基亚S60系列(屏幕176*220)手机以及其他大屏手机(小屏游戏也可运行,但不能全屏显示),是一款非常简单而且实用的java游戏模拟器,可以正常运行绝大部分JAVA手机游戏!应用特点:Java语言的一个非常重要的特点就是与平台的无关性。而使用Java虚拟机是实现这一特…

  • 【转载】VS工具使用——代码图

    【转载】VS工具使用——代码图

    2021年11月18日
  • Spring获取request对象的几种方式[通俗易懂]

    Spring获取request对象的几种方式[通俗易懂]参考文章:在SpringMVC中获取request对象的几种方式Springboot获取request和response使用Springboot,我们很多时候直接使用@PathVariable、@RequestParam、@Param来获取参数,但是偶尔还是要用到request和response,怎么获取呢?也很方便,有三种方式可以获取,任选其一就行。1、通过静态方法…

  • Win10安装jdk11及环境变量配置

    Win10安装jdk11及环境变量配置Win10安装jdk11及环境变量配置写在前面卸载旧版本jdk下载jdk11配置环境变量经验教训写在前面我第一次安装java是在17年初,距离现在已经一年半了。今天上oracle官网一看,jdk都已经更新到11.0.1了,然而我用的还是1.8.0_171版本的老古董,遂决定把jdk升级一下,结果没想到这一升级就折腾了老半天。在这里把我的升级的详细步骤以及经验教训和大家分享一下。卸载旧版本jd…

  • Idea激活码永久有效Idea2017.3.6激活码教程-持续更新,一步到位

    Idea激活码永久有效Idea2017.3.6激活码教程-持续更新,一步到位Idea激活码永久有效2017.3.6激活码教程-Windows版永久激活-持续更新,Idea激活码2017.3.6成功激活

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号