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

洛谷-最长公共子串「建议收藏」原题链接题目描述给定两个字符串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)


相关推荐

  • CRTMP视频直播服务器部署及测试

    CRTMP视频直播服务器部署及测试一、搭建CRTMP视频直播服务器1、下载CRTMP服务器软件svnco–usernameanonymous–password””https://svn.rtmpd.com/crtmpserver/trunkcrtmpserver2、进入一下目录,

  • tomcat java_tomcat和maven的区别

    tomcat java_tomcat和maven的区别缓存什么是缓存[Cache]存在内存中的临时数据将用户经常查询的数据放在缓存(内存)中,用户去查询数据的时候就不用从磁盘上(关系型数据库数据文件)查询,从缓存中查询,从而提高查询效率,解决了高并发系统的性能问题。为什么使用缓存减少和数据库的数据交换次数,较少系统开销,提高系统效率什么样的数据库能使用缓存经常查询并且不经常改变的数据Mybatis缓存MyBatis 内置了一个强大的事务性查询缓存机制,它可以非常方便地配置和定制。默认情况下,只启用了本地的会话缓存,它仅

  • 剑指Offer面试题:1.实现单例模式建议收藏

    一题目:实现单例模式Singleton只能生成一个实例的类是实现了Singleton(单例)模式的类型。由于设计模式在面向对象程序设计中起着举足轻重的作用,在面试过程中很多公司都喜欢问一些与设计模

    2021年12月19日
  • Dreamweaver CS6 完全自学教程 (一)[通俗易懂]

    Dreamweaver CS6 完全自学教程 (一)[通俗易懂]DreamweaverCS6完全自学教程DreamweaverCS6教程下载地址(百度网盘):https://pan.baidu.com/s/1fIUk4O36JCNVCfOQSH22vw百度网盘下载(压缩包):https://pan.baidu.com/s/17G11dm_uXFCWVn5y…

  • Java连接MySQL mysql-connector-java-bin.jar驱动包的下载与安装

    Java连接MySQL mysql-connector-java-bin.jar驱动包的下载与安装eclipse在连接mysql数据库的时候要通过mysql驱动包进行连接首先进入官网中—-官网地址:https://dev.mysql.com/进入官网中选择DOWNLOADS(下载)2.选择下载中的mysql-connectors3.选择connector/JJ指的是Java4.接下在选择操作系统,此处选择platformindependent(独立于平台)…

  • DeepLab 笔记

    2019March10deeplabDeepLab笔记一、背景DCNN存在的问题:多次下采样使输出信号分辨率变小——空洞卷积池化对输入变换具有内在空间不变性——CRF二、空洞卷积1.作用保证感受野不发生变化得到密集的featuremap2.卷积核new\_kernel=kernel+\left(kernel-1\right…

发表回复

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

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