当前位置: 首页 > news >正文

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 题面翻译 题目描述&#xff1a; 给定一个字符串 s s s 和一个字符串 t t t &#xff0c;输出 s s s 和 t t t 的最长公共子序列。 输入格式&#xff1a; 两行&#xff0c;第一行输入 s s s &#xff0c;第二行输入 t t t 。 输出格式&#xff1a; 输出 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程序设计&#xff08;扩展一&#xff09; **注意&#xff1a;**开启本视频学习前&#xff0c;需要先完成以下内容的学习&#xff1a; 请先完成《Kotlin程序设计》视频教程。请先完成《JavaSE》视频教程。 Kotlin在设计时考虑到了与Java的互操作性&#xff0c;现有的Ja…...

星环科技基于第五代英特尔®至强®可扩展处理器的分布式向量数据库解决方案重磅发布

12月15日&#xff0c;2023 英特尔新品发布会暨 AI 技术创新派对上&#xff0c;星环科技基于第五代英特尔至强可扩展处理器的Transwarp Hippo分布式向量数据库解决方案重磅发布。该方案利用第五代英特尔至强可扩展处理器带来的强大算力&#xff0c;实现了约 2 倍的代际性能提升&…...

一体化运维的发展趋势与未来展望

随着信息技术的迅猛发展&#xff0c;企业的IT系统已经从单一的、孤立的应用转变为多元化、复杂化的系统集群。云计算、大数据、物联网等前沿技术的广泛应用&#xff0c;使得企业的IT运维面临着前所未有的挑战。在这样的背景下&#xff0c;一体化运维作为一种新型的运维模式&…...

科技云报道:金融大模型落地,还需跨越几重山?

科技云报道原创。 时至今日&#xff0c;大模型的狂欢盛宴仍在持续&#xff0c;而金融行业得益于数据密集且有强劲的数字化基础&#xff0c;从一众场景中脱颖而出。 越来越多的公司开始布局金融行业大模型&#xff0c;无论是乐信、奇富科技、度小满、蚂蚁这样的金融科技公司&a…...

C语言入门到精通之练习34:求100之内的素数

题目&#xff1a;求100之内的素数。 程序分析&#xff1a;质数&#xff08;素数&#xff09;酵母素数&#xff0c;有无限个。一个大于1的自然数&#xff0c;除了1和它本身外&#xff0c;不能被其他自然数整除。 代码如下&#xff1a; #include <stdio.h># #include &l…...

Qt采集本地摄像头推流成rtsp/rtmp(可网页播放/支持嵌入式linux)

一、功能特点 支持各种本地视频文件和网络视频文件。支持各种网络视频流&#xff0c;网络摄像头&#xff0c;协议包括rtsp、rtmp、http。支持将本地摄像头设备推流&#xff0c;可指定分辨率和帧率等。支持将本地桌面推流&#xff0c;可指定屏幕区域和帧率等。自动启动流媒体服…...

Oracle按日周月年自动分区

目录 1、分区键 2、初始分区 3、周月年自动分区 4、按日自动分区表建表语句 与普通建表语句相比&#xff0c;分区表多了一些分区信息&#xff1b; 1、分区键 以下面销售明细表为例&#xff0c;以data_dt为分区键&#xff0c;NUMTODSINTERVAL(1, day) 按日分区 PARTITION …...

单元测试、模块测试、web接口测试

单元测试与模块测试 什么是“单元测试”、“模块测试”&#xff1f; 然而在功能的实现代码中并没有“单元”&#xff0c;也没有“模块”&#xff1b;只有函数、类和方法。先来分别看看它们 的定义&#xff1a; 单元测试&#xff08;Unit testing&#xff09;&#xff0c;是指…...

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 一刷 笔记

安全感来自确定性&#xff0c;但机会藏在不确定性中 安全感来自确定性&#xff0c;但机会藏在不确定性中。 每一个弯道里&#xff0c;都有你超车的机会 意外、周期、趋势、规划 可是&#xff0c;为什么趋势一定是不可逆转的呢&#xff1f;因为&#xff0c;效率提高了 长期…...

用Excel辅助做数独

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

arcgis实现截图/截屏功能

arcgis实现截图/截屏功能 文章目录 arcgis实现截图/截屏功能前言效果展示相关代码 前言 本篇将使用arcgis实现截图/截屏功能&#xff0c;类似于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 表单处理 学习目标&#xff1a; 能够使用受控组件的方式获取文本框 使用 React 处理表单一般有两种方法 受控组件 &#xff08;推荐&#xff09;非受控组件 &#xff08;了解&#xff09; 1. 受控表单组件 什么是受控组件&#xff1f; input 框自己的状态被 React 组…...

Android开发--状态栏布局隐藏的方法

1.问题如下&#xff0c;安卓布局很不协调 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是华为自主创新研发的分布式关系型数据库&#xff0c;为企业提供功能全面、稳定可靠、扩展性强、性能优越的企业级数据库服务。在实际业务场景使用中&#xff0c;为了提高工作效率&#xff0c;数据库GaussDB提供定时任务的功能&#xff0c;本节为大家讲解GaussDB如…...

mybatis-plus:代码生成器

一、依赖 代码生成器需要添加一下依赖 <dependencies><dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-generator</artifactId><version>3.0.7.1</version></dependency><!-- https://mvnre…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...