【C++】【算法基础】序列编辑距离
编辑距离
题目
给定 n n n个长度不超过 10 10 10 的字符串以及 m m m 次询问,每次询问给出一个字符串和一个操作次数上限。
对于每次询问,请你求出给定的 n n n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
详见899. 编辑距离 - AcWing题库
输入格式
第一行包含两个整数 n n n和 m m m。
接下来 n n n 行,每行包含一个字符串,表示给定的字符串。
再接下来 m m m 行,每行包含一个字符串和一个整数,表示一次询问。
字符串中只包含小写字母,且长度均不超过 10 10 10。
输出格式
输出共 m m m行,每行输出一个整数作为结果,表示一次询问中满足条件的字符串个数。
// input:
3 2
abc
acd
bcd
ab 1
acbd 2
// output:
1
3
题解
总的思路就是对于在每次询问中将每个序列的最少编辑距离得出,在分别与操作次数上限相比即可:
#include <iostream>
#include <cstring>
using namespace std;int n, m, f[1005][1005], len_1[1005], len_2, t;
char a[1005][1005], b[1005];int main()
{cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];len_1[i] = strlen(a[i]); }while(m --){int cnt = 0;cin >> b >> t;len_2 = strlen(b); for(int k = 1; k <= n; k++){for(int i = 0; i <= len_1[k]; i++) f[i][0] = i;for(int j = 0; j <= len_2; j++) f[0][j] = j;for(int i = 1; i <= len_1[k]; i++)for(int j = 1; j <= len_2; j++){f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[k][i - 1] != b[j - 1]));}if(f[len_1[k]][len_2] <= t) cnt++;}cout << cnt << endl;}return 0;
}
相关文章:
【C++】【算法基础】序列编辑距离
编辑距离 题目 给定 n n n个长度不超过 10 10 10 的字符串以及 m m m 次询问,每次询问给出一个字符串和一个操作次数上限。 对于每次询问,请你求出给定的 n n n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。 每个…...
【Android】轮播图——Banner
引言 Banner轮播图是一种在网页和移动应用界面设计中常见的元素,主要用于在一个固定的区域内自动或手动切换一系列图片,以展示不同的内容或信息。这个控件在软件当中经常看到,商品促销、热门歌单、头像新闻等等。它不同于ViewPgaer在于无需手…...
学SQL,要安装什么软件?
先上结论,推荐MySQLDbeaver的组合。 学SQL需要安装软件吗? 记得几年前我学习SQL的时候,以为像Java、Python一样需要安装SQL软件包,后来知道并没有所谓SQL软件,因为SQL是一种查询语言,它用来对数据库进行操…...
webstorm 设置总结
编辑器-》文件类型-》忽略的文件和文件夹-》加上node_modules 修改WebStorm 内存有两种方式。 1. 点击菜单中的Help -> change memory settings 弹出设置内存窗口,修改最大内存大小。然后点击Save and Restart 即可。 2. 点击菜单中的Help -> Edit Custom V…...
基于Spring Boot的养老保险管理系统的设计与实现,LW+源码+讲解
摘 要 如今社会上各行各业,都喜欢用自己行业的专属软件工作,互联网发展到这个时候,人们已经发现离不开了互联网。新技术的产生,往往能解决一些老技术的弊端问题。因为传统养老保险管理系统信息管理难度大,容错率低&a…...
Java | Leetcode Java题解之第541题反转字符串II
题目: 题解: class Solution {public String reverseStr(String s, int k) {int n s.length();char[] arr s.toCharArray();for (int i 0; i < n; i 2 * k) {reverse(arr, i, Math.min(i k, n) - 1);}return new String(arr);}public void reve…...
sql分区
将学员表student按所在城市使用PARTITION BY LIST 1、创建分区表。 CREATE TABLE public.student( sno numeric(4,0), sname character varying(20 char),gender character varying(2 char), phone numeric(11,0), …...
[OpenGL]使用OpenGL实现硬阴影效果
一、简介 本文介绍了如何使用OpenGL实现硬阴影效果,并在最后给出了全部的代码。本文基于[OpenGL]渲染Shadow Map,实现硬阴影的流程如下: 首先,以光源为视角,渲染场景的深度图,将light space中的深度图存储…...
嵌入式采集网关(golang版本)
为了一次编写到处运行,使用纯GO编写,排除CGO,解决在嵌入式中交叉编译难问题 硬件设备:移远EC200A-CN LTE Cat 4 无线通信模块,搭载openwrt操作系统,90M内存...
ctfshow(328)--XSS漏洞--存储型XSS
Web328 简单阅读一下页面。 是一个登录系统,存在一个用户管理数据库。 那么我们注册一个账号,在账号或者密码中植入HTML恶意代码,当管理员访问用户管理数据库页面时,就会触发我们的恶意代码。 思路 我们向数据库中写入盗取管理员…...
【C#】Thread.CurrentThread的用法
Thread.CurrentThread 是 System.Threading.Thread 类的一个静态属性,它返回当前正在执行的线程对象。通过 Thread.CurrentThread,可以访问和修改当前线程的各种属性和方法。 下面是一些常见的用法和示例: 1. 获取当前线程的信息 使用 Thr…...
简单分享一下淘宝商品数据自动化抓取的技术实现与挑战
在电子商务领域,数据是驱动决策的关键。淘宝作为国内最大的电商平台之一,其商品数据对电商从业者来说具有极高的价值。然而,从淘宝平台自动化抓取商品数据并非易事,涉及多重技术和法律挑战。本文将从技术层面分析实现淘宝商品数据…...
Netty篇(入门编程)
目录 一、Hello World 1. 目标 2. 服务器端 3. 客户端 4. 流程梳理 💡 提示 5. 运行结果截图 二、Netty执行流程 1. 流程分析 2. 代码案例 2.1. 引入依赖 2.2. 服务端 服务端 服务端处理器 2.3. 客户端 客户端 客户端处理器 2.4. 代码截图 一、Hel…...
【渗透测试】payload记录
Java开发使用char[]代替String保存敏感数据 Java Jvm会提供内存转储功能,当Java程序dump后,会生成堆内存的快照,保存在.hprof后缀的文件中,进而导致敏感信息的泄露。char[]可以在存储敏感数据后手动清零,String对象会…...
2024自动驾驶线控底盘行业研究报告
自动驾驶线控底盘是实现自动驾驶的关键技术之一,它通过电子信号来控制车辆的行驶,包括转向、制动、驱动、换挡和悬架等系统。线控底盘技术的发展对于自动驾驶汽车的实现至关重要,因为它提供了快速响应和精确控制的能力,这是自动驾驶系统所必需的。 线控底盘由五大系统组成…...
css3D变换用法
文章目录 CSS3D变换详解及代码案例一、CSS3D变换的基本概念二、3D变换的开启与景深设置三、代码案例 CSS3D变换详解及代码案例 CSS3D变换是CSS3中引入的一种强大功能,它允许开发者在网页上创建三维空间中的动画和交互效果。通过CSS3D变换,你可以实现元素…...
Rust:启动与关闭线程
在 Rust 编程中,启动和关闭线程是并发编程的重要部分。Rust 提供了强大的线程支持,允许你轻松地创建和管理线程。下面将详细解释如何在 Rust 中启动和关闭线程。 启动线程 在 Rust 中,你可以使用标准库中的 std::thread 模块来创建和启动新…...
Ubuntu 的 ROS 2 操作系统安装与测试
引言 机器人操作系统(ROS, Robot Operating System)是一种广泛应用于机器人开发的开源框架,提供了丰富的库和工具,支持开发者快速构建、控制机器人并实现智能功能。 当前,ROS 2 的最新长期支持版本为 Humble Hawksbil…...
在双显示器环境中利用Sunshine与Moonlight实现游戏串流的同时与电脑其他任务互不干扰
我和老婆经常会同时需要操作家里的电脑,在周末老婆有时要用电脑加班上网办公,而我想在难得的周末好好地Game一下(在客厅用电视机或者平板串流),但是电脑只有一个,以往我一直都是把电脑让给老婆,…...
ElasticSearch备考 -- Cross cluster replication(CCR)
一、题目 操作在cluster1(local)中操作索引task,复制到cluster2(remote)中 二、思考 CCR 我们可以对标MySQL 理解为为主从,后者备份。主节点负责写入数据,从/备节点负责同步时主节点的数据。 …...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
