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

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

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

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

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...