LCS板子加逆向搜索
LCS
题面翻译
题目描述:
给定一个字符串 s s s 和一个字符串 t t t ,输出 s s s 和 t t t 的最长公共子序列。
输入格式:
两行,第一行输入 s s s ,第二行输入 t t t 。
输出格式:
输出 s s s 和 t t t 的最长公共子序列。如果有多种答案,输出任何一个都可以。
说明/提示:
数据保证 s s s 和 t t t 仅含英文小写字母,并且 s s s 和 t t t 的长度小于等于3000。
题目描述
文字列 $ s $ および $ t $ が与えられます。 $ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
$ s $ $ t $
输出格式
$ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ出力せよ。 答えが複数ある場合、どれを出力してもよい。
样例 #1
样例输入 #1
axyb
abyxb
样例输出 #1
axb
样例 #2
样例输入 #2
aa
xayaz
样例输出 #2
aa
样例 #3
样例输入 #3
a
z
样例输出 #3
样例 #4
样例输入 #4
abracadabra
avadakedavra
样例输出 #4
aaadara
提示
注釈
文字列 $ x $ の部分列とは、$ x $ から $ 0 $ 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。
制約
- $ s $ および $ t $ は英小文字からなる文字列である。
- $ 1\ \leq\ |s|,\ |t|\ \leq\ 3000 $
Sample Explanation 1
答えは axb
または ayb
です。 どちらを出力しても正解となります。
Sample Explanation 3
答えは `` (空文字列) です。
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXS 3002
char arr1[MAXS], arr2[MAXS],ans[MAXS];
int dp[MAXS][MAXS],ans_num;
int main(void)
{ios::sync_with_stdio(0);cin >> arr1 >> arr2;int s1 = strlen(arr1), s2 = strlen(arr2);for (int i = 0; i < s1; i++){for (int j = 0; j < s2; j++){if (arr1[i] == arr2[j]){dp[i + 1][j + 1] = dp[i][j] + 1;}else{dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);}}}
//以上为板子int i = s1-1,j = s2-1 ;while(dp[i+1][j+1]>0){while (dp[i+1][j+1] == dp[i][j+1])//i指向的arr1【i】不是公共子序列的一部分{i--;}//现在i指向了公共子序列的一部分while (j>=0&&arr1[i] != arr2[j]){j--;}//现在i和j指向的字母相同ans[ans_num] = arr1[i];ans_num++;i--; j--;}for (int i = ans_num - 1; i >= 0; i--){cout << ans[i];}return 0;
}
相关文章:
LCS板子加逆向搜索
LCS 题面翻译 题目描述: 给定一个字符串 s s s 和一个字符串 t t t ,输出 s s s 和 t t t 的最长公共子序列。 输入格式: 两行,第一行输入 s s s ,第二行输入 t t t 。 输出格式: 输出 s s s…...

不同知识表示方法与知识图谱
目录 前言1 一阶谓词逻辑1.1 简介1.2 优势1.3 局限性 2 产生式规则2.1 简介2.2 优势2.3 局限性 3 框架系统3.1 简介3.2 优势3.3 局限性 4 描述逻辑4.1 简介4.2 优势4.3 局限性 5 语义网络5.1 简介5.2 优势5.3 局限性 结语 前言 知识表示是人工智能领域中至关重要的一环&#x…...

Kotlin程序设计 扩展篇(一)
Kotlin程序设计(扩展一) **注意:**开启本视频学习前,需要先完成以下内容的学习: 请先完成《Kotlin程序设计》视频教程。请先完成《JavaSE》视频教程。 Kotlin在设计时考虑到了与Java的互操作性,现有的Ja…...

星环科技基于第五代英特尔®至强®可扩展处理器的分布式向量数据库解决方案重磅发布
12月15日,2023 英特尔新品发布会暨 AI 技术创新派对上,星环科技基于第五代英特尔至强可扩展处理器的Transwarp Hippo分布式向量数据库解决方案重磅发布。该方案利用第五代英特尔至强可扩展处理器带来的强大算力,实现了约 2 倍的代际性能提升&…...
一体化运维的发展趋势与未来展望
随着信息技术的迅猛发展,企业的IT系统已经从单一的、孤立的应用转变为多元化、复杂化的系统集群。云计算、大数据、物联网等前沿技术的广泛应用,使得企业的IT运维面临着前所未有的挑战。在这样的背景下,一体化运维作为一种新型的运维模式&…...

科技云报道:金融大模型落地,还需跨越几重山?
科技云报道原创。 时至今日,大模型的狂欢盛宴仍在持续,而金融行业得益于数据密集且有强劲的数字化基础,从一众场景中脱颖而出。 越来越多的公司开始布局金融行业大模型,无论是乐信、奇富科技、度小满、蚂蚁这样的金融科技公司&a…...
C语言入门到精通之练习34:求100之内的素数
题目:求100之内的素数。 程序分析:质数(素数)酵母素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除。 代码如下: #include <stdio.h># #include &l…...

Qt采集本地摄像头推流成rtsp/rtmp(可网页播放/支持嵌入式linux)
一、功能特点 支持各种本地视频文件和网络视频文件。支持各种网络视频流,网络摄像头,协议包括rtsp、rtmp、http。支持将本地摄像头设备推流,可指定分辨率和帧率等。支持将本地桌面推流,可指定屏幕区域和帧率等。自动启动流媒体服…...
Oracle按日周月年自动分区
目录 1、分区键 2、初始分区 3、周月年自动分区 4、按日自动分区表建表语句 与普通建表语句相比,分区表多了一些分区信息; 1、分区键 以下面销售明细表为例,以data_dt为分区键,NUMTODSINTERVAL(1, day) 按日分区 PARTITION …...

单元测试、模块测试、web接口测试
单元测试与模块测试 什么是“单元测试”、“模块测试”? 然而在功能的实现代码中并没有“单元”,也没有“模块”;只有函数、类和方法。先来分别看看它们 的定义: 单元测试(Unit testing),是指…...

DAY10_SpringBoot—SpringMVC重定向和转发RestFul风格JSON格式SSM框架整合Ajax-JQuery
目录 1 SpringMVC1.1 重定向和转发1.1.1 转发1.1.2 重定向1.1.3 转发练习1.1.4 重定向练习1.1.5 重定向/转发特点1.1.6 重定向/转发意义 1.2 RestFul风格1.2.1 RestFul入门案例1.2.2 简化业务调用 1.3 JSON1.3.1 JSON介绍1.3.2 JSON格式1.3.2.1 Object格式1.3.2.2 Array格式1.3…...
刘润-进化的力量2 一刷 笔记
安全感来自确定性,但机会藏在不确定性中 安全感来自确定性,但机会藏在不确定性中。 每一个弯道里,都有你超车的机会 意外、周期、趋势、规划 可是,为什么趋势一定是不可逆转的呢?因为,效率提高了 长期…...

用Excel辅助做数独
做数独游戏的时候,画在纸上很容易弄花眼,所以我考虑用Excel辅助做一个。 界面如下: 按下初始化表格区域按钮,会在所有单元格中填充“123456789”。如下图: 当某个单元格删除得只剩一个数字时,会将同一行、…...

arcgis实现截图/截屏功能
arcgis实现截图/截屏功能 文章目录 arcgis实现截图/截屏功能前言效果展示相关代码 前言 本篇将使用arcgis实现截图/截屏功能,类似于qq截图 效果展示 相关代码 <!DOCTYPE html> <html> <head><meta charset"utf-8"><meta nam…...
mysql备份
1.新建备份目录 mkdir -p /data/mysql_dump/#查找mysql配置位置 find / -name "my.cnf" find / -name "mysql.sock" find / -name "mysqldump"2.定时任务 #每天凌晨备份一次 echo "00 00 * * * root /data/mysql_bak.sh" >> /…...
CentOS7 安装PostgreSQL以及配置服务
文章目录 前言1. 安装步骤2. 连接PostgreSQL3. 配置服务配置文件所在路径设置监听地址修改数据库密码已经修改了密码,为什么没有生效?不需要密码就可以连接?设置访问权限4. 新的配置生效前言 PostgreSQL是一种功能强大的开源关系型数据库管理系统,被广泛用于各种应用程序和…...
React 表单、处理受控表单组件、非受控组件
React 表单处理 学习目标: 能够使用受控组件的方式获取文本框 使用 React 处理表单一般有两种方法 受控组件 (推荐)非受控组件 (了解) 1. 受控表单组件 什么是受控组件? input 框自己的状态被 React 组…...

Android开发--状态栏布局隐藏的方法
1.问题如下,安卓布局很不协调 2.先将ActionBar设置为NoActionBar 先打开styles.xml 3.使用工具类 package com.afison.newfault.utils;import android.annotation.TargetApi; import android.app.Activity; import android.content.Context; import android.graph…...
GaussDB如何创建和管理序列、定时任务
前言 GaussDB是华为自主创新研发的分布式关系型数据库,为企业提供功能全面、稳定可靠、扩展性强、性能优越的企业级数据库服务。在实际业务场景使用中,为了提高工作效率,数据库GaussDB提供定时任务的功能,本节为大家讲解GaussDB如…...
mybatis-plus:代码生成器
一、依赖 代码生成器需要添加一下依赖 <dependencies><dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-generator</artifactId><version>3.0.7.1</version></dependency><!-- https://mvnre…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...