【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 理解为为主从,后者备份。主节点负责写入数据,从/备节点负责同步时主节点的数据。 …...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
