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

Trie树(字典树)

原理:

        1. ch[p][j]:p是每个单词存到的idx索引,j是存入字符映射的数字

        2. cnt[p] 存这个单词个数

【模板】字典树 - 洛谷

#include <iostream>
#include <cstring>
using namespace std;const int N = 3e6 + 10;
int ch[N][100], idx;
int cnt[N];
char str[N];int convert(char s) { // 哈希映射if(s >= 'A' && s <= 'Z')return s - 'A';else if(s >= 'a' && s <= 'z')return s - 'a' + 26;else return s - '0' + 52;
}void insert(char s[]) {int p = 0;for(int i = 0; i < strlen(s); i ++ ) {int j = convert(s[i]);if(!ch[p][j]) ch[p][j] = ++ idx;p = ch[p][j];cnt[p] ++;}}int query(char s[]) {int p = 0;for(int i = 0; i < strlen(s); i ++ ) {int j = convert(s[i]);if(!ch[p][j]) return 0;p = ch[p][j];}return cnt[p];
}
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n; cin >> n;while(n -- ) {// 回归初始状态for(int i = 0; i <= idx; i ++ ) {for(int j = 0; j <= 122; j ++ ) {ch[i][j] = 0;}}for(int i = 0; i <= idx; i ++ ) {cnt[i] = 0;}idx = 0;int q, t;cin >> q >> t;for(int i = 1; i <= q; i ++ ) {cin >> str;insert(str);}for(int i = 1; i <= t; i ++ ) {cin >> str;cout << query(str) << endl;}}return 0;
}

相关文章:

Trie树(字典树)

原理&#xff1a; 1. ch[p][j]:p是每个单词存到的idx索引&#xff0c;j是存入字符映射的数字 2. cnt[p] 存这个单词个数 【模板】字典树 - 洛谷 #include <iostream> #include <cstring> using namespace std;const int N 3e6 10; int ch[N][100], idx; int cnt…...

华为政企网络安全产品集

产品类型产品型号产品说明 防火墙及应用安全网关ASG5505ASG5000系列上网行为管理产品&#xff08;以下简称“ASG5000”&#xff09;是华为面向各类企业、政府、大中型数据中心以及各类无线非经营性场所推出的业界领先的综合上网行为管理产品。 该系列产品可深度识别、管控和…...

02-Sping事务实现之声明式事务基于XML的实现方式

声明式事务之XML实现方式 开发步骤 第一步: 引入AOP相关的aspectj依赖 <!--aspectj依赖--> <dependency><groupId>org.springframework</groupId><artifactId>spring-aspects</artifactId><version>6.0.0-M2</version> <…...

桶装水订水系统水厂送水小程序开发;

桶装水小程序正式上线&#xff0c;支持多种商品展示形式&#xff0c;会员卡、积分、分销等功能&#xff1b; 开发订水送水小程序系统&#xff0c;基于用户、员工、商品、订单、配送站和售后管理模块&#xff0c;对每个模块进行统计分析&#xff0c;简化了分配过程&#xff0c;提…...

png或jpg等图片文件转ico图标文件,格式在线转换

图片文件转ico图标文件在线转换&#xff1a;在线转换图片格式-在线图片转换器-100% 免费 (jinaconvert.com)...

操作系统——对文件的 基本操作(王道视频p65)

1.总体概述&#xff1a; 2.进程打开文件表 和 系统打开文件表&#xff1a;...

中海达守护电力人员作业安全

近日&#xff0c;中海达为电网某换流站作业人员提供的160余套北斗高精度定位产品顺利完成交付。通过使用北斗高精度定位技术&#xff0c;帮助换流站实现了人员&#xff08;车辆&#xff09;位置实时定位、电子围栏实时预警、远程作业指导等应用效果&#xff0c;用高科技保障电网…...

想学计算机编程从什么学起?零基础如何自学计算机编程?中文编程开发语言工具箱之渐变标签组构件

想学计算机编程从什么学起&#xff1f;零基础如何自学计算机编程&#xff1f; 给大家分享一款中文编程工具&#xff0c;零基础轻松学编程&#xff0c;不需英语基础&#xff0c;编程工具可下载。 这款工具不但可以连接部分硬件&#xff0c;而且可以开发大型的软件&#xff0c;…...

中国人民大学与加拿大女王大学金融硕士——一把开启未来金融世界的金钥匙

在这个日新月异、竞争激烈的时代&#xff0c;每个人都渴望不断提升自我&#xff0c;以应对不断变化的世界。在当今的金融领域&#xff0c;国际化的视野和多元化的知识结构变得越来越重要。如何才能掌握未来世界的金钥匙呢&#xff1f;其实&#xff0c;这把金钥匙并非遥不可及&a…...

MVC、MVP、MVVM区别

MVC、MVP、MVVM区别 MVC&#xff08;Model-View-Controller&#xff09; 。是一种设计模式&#xff0c;通常用于组织与应用程序的数据流。它通常包括三个组件&#xff1a;模型&#xff08;Model&#xff09;、视图&#xff08;View&#xff09;和控制器&#xff08;Controller&…...

【Kotlin精简】第7章 泛型

1 泛型 泛型即 “参数化类型”&#xff0c;将类型参数化&#xff0c;可以用在类&#xff0c;接口&#xff0c;函数上。与 Java 一样&#xff0c;Kotlin 也提供泛型&#xff0c;为类型安全提供保证&#xff0c;消除类型强转的烦恼。 1.1 泛型优点 类型安全&#xff1a;通用允许…...

ElasticSearch与Lucene是什么关系?Lucene又是什么?

一. ElasticSearch 与 Lucene 的关系 Elasticsearch&#xff08;ES&#xff09;和Apache Lucene之间有密切的关系&#xff0c;可以总结如下&#xff1a; Elasticsearch构建于Lucene之上&#xff1a;Elasticsearch实际上是一个分布式的、实时的搜索和分析引擎&#xff0c;它构建…...

【算法练习Day40】打家劫舍打家劫舍 II打家劫舍 III

​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;练题 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录 打家劫舍打家劫舍 II打家劫…...

双十一运动健身好物推荐,这几款健身好物一定不要错过!

双十一购物狂欢节又要到了&#xff0c;又要到买买买的时候了&#xff01;相信有很多想健身的小白还在发愁不知道买啥装备&#xff1f;别急&#xff0c;三年健身达人这就给你们分享我的年度健身好物&#xff01; 第一款&#xff1a;南卡Runner Pro4s骨传导耳机 推荐理由&#…...

Angular异步数据流编程

1 目前常见的异步编程的几种方法 首先给出一个异步请求的实例&#xff1a; import {Injectable} from angular/core;Injectable({providedIn: root }) export class RequestServiceService {constructor() {}getData() {setTimeout(() > {let res zhaoshuai-lcreturn res…...

古典舞学习的独舞与群舞,古典舞的成品舞蹈教学大全

一、教程描述 本套教程的古典舞是很全面的&#xff0c;不仅有舞蹈动作分解教学&#xff0c;而且有成品舞的完整教学&#xff0c;同时提供独立的背景音乐文件&#xff0c;可以让你更快地学会古典舞。本套教程&#xff0c;大小30.54G&#xff0c;共有276个文件。 二、教程目录 …...

听GPT 讲Rust源代码--library/std(16)

题图来自 EVALUATION OF RUST USAGE IN SPACE APPLICATIONS BY DEVELOPING BSP AND RTOS TARGETING SAMV71[1] File: rust/library/std/src/sync/mpmc/select.rs 在Rust标准库中&#xff0c;rust/library/std/src/sync/mpmc/select.rs文件的作用是实现一个多生产者多消费者的选…...

计算机编程软件编程基础知识,中文编程工具下载分享

计算机编程软件编程基础知识&#xff0c;中文编程工具下载分享 给大家分享一款中文编程工具&#xff0c;零基础轻松学编程&#xff0c;不需英语基础&#xff0c;编程工具可下载。 这款工具不但可以连接部分硬件&#xff0c;而且可以开发大型的软件&#xff0c;象如图这个实例…...

微信小程序里怎么添加砍价活动

随着网络购物的普及&#xff0c;越来越多的消费者开始享受这种方便快捷的购物方式。而在这个大环境下&#xff0c;各种电商活动层出不穷&#xff0c;吸引了众多消费者的关注。而在这些活动中&#xff0c;砍价活动无疑是最受欢迎的一种。今天&#xff0c;我们就来聊一聊如何在小…...

如何在Python爬虫中使用IP代理以避免反爬虫机制

目录 前言 一、IP代理的使用 1. 什么是IP代理&#xff1f; 2. 如何获取IP代理&#xff1f; 3. 如何使用IP代理&#xff1f; 4. 如何避免IP代理失效&#xff1f; 5. 代理IP的匿名性 二、代码示例 总结 前言 在进行爬虫时&#xff0c;我们很容易会遇到反爬虫机制。网站…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

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…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...