【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 理解为为主从,后者备份。主节点负责写入数据,从/备节点负责同步时主节点的数据。 …...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
