当前位置: 首页 > 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;我们很容易会遇到反爬虫机制。网站…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...