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

C++自定义字典树结构

代码 
#include <iostream>
using namespace std;class TrieNode
{
public:char data;TrieNode* children[26];bool isTerminal;TrieNode(char ch){data = ch;for (int i = 0; i < 26; i++){children[i] = NULL;}isTerminal = false;}
};
class Trie
{
public:TrieNode* root;Trie(){root = new TrieNode('\0');}void insertUtil(TrieNode* root, string word){// base caseif (word.length() == 0){root->isTerminal = true;return;}// assumption , world will be CAPSint index = word[0] - 'A';TrieNode* child;// presentif (root->children[index] != NULL){child = root->children[index];}else{// absentchild = new TrieNode(word[0]);root->children[index] = child;}// RECURSIONinsertUtil(child, word.substr(1));}void insertWord(string word){insertUtil(root, word);}bool searchUtil(TrieNode* root, string word){// base caseif (word.length() == 0){return root->isTerminal;}int index = word[0] - 'A';TrieNode* child;// presentif (root->children[index] != NULL){child = root->children[index];}else{// absentreturn false;}// RECURSIONreturn searchUtil(child, word.substr(1));}bool searchWord(string word){return searchUtil(root, word);}
};#include <bitset>
#include <unordered_map>
#include <vector>
template <std::size_t N>
using Signature = std::bitset<N>;// util function to split string into parts by given delimiter.
static void split(std::string_view s, std::vector<std::string>& parts, char delimiter) {parts.emplace_back();for (auto ch : s) ch == delimiter ? parts.push_back("") : parts.back().push_back(ch);
};// A MyTrie structures ids by names into a tree.
template <std::size_t N>
class MyTrie {
private:// Signature of all signals under this tree.// e.g. the node `b` matches all "a.b.*"Signature<N> signature;// Child tries.std::unordered_map<std::string, MyTrie*> children;// If it's a end node of a signal's name, the signal id of which.size_t id = 0;char m_delimiter;public:MyTrie(char delimiter = '.') : m_delimiter(delimiter){}~MyTrie() {  // free every child recursivelyfor (auto p : children) delete p.second;}// Puts a signal id onto this tree by signal name.void Put(std::string_view name, size_t id) {std::vector<std::string> parts;split(name, parts, m_delimiter);auto t = this;  // t is the node walked throughfor (const auto& p : parts) {// Creates a node if not exist.if (auto [it, inserted] = t->children.try_emplace(p, nullptr); inserted) it->second = new MyTrie();// Mark this signal id to its signature.t->signature[id] = 1;t = t->children[p];}// The last node.t->id = id;}// Match signals by given pattern, returns a signature of matched signal ids.Signature<N> Match(std::string_view pattern) const {Signature<N> sig;std::vector<std::string> parts;split(pattern, parts, m_delimiter);auto t = this;for (const auto& p : parts) {// matches all under the subtreeif (p == "*")return t->signature;else {  // match by exact name// match failure, returns empty signatureif (t->children.find(p) == t->children.end()) return sig;t = t->children.at(p);}}// The last node, matches a single signal.sig[t->id] = 1;return sig;}
};int test()
{// 基础添加查找,单个字符为一组,进行字符串词典构建Trie* t = new Trie();t->insertWord("ARM");t->insertWord("DO");t->insertWord("TIME");cout << "Present or Not " << t->searchWord("TIM") << endl;  // Present or Not 0cout << "Present or Not " << t->searchWord("TIME") << endl; // Present or Not 1// 扩展模式匹配,单个字符串为一组,进行字符串词典构建MyTrie<1024> trie;trie.Put("ab.cd.ef", 1);trie.Put("ab.cd.kk", 2);trie.Put("ab.xy.zz", 3);trie.Put("tt.xx", 4);trie.Put("ab.cd", 5);auto m1 = trie.Match("ab.cd.ef");   // m1.count() == 1auto m2 = trie.Match("ab.cd.*");   // m2.count() == 2// 字体查找MyTrie<1024> fontlist(' ');std::vector<std::string> familys = {"Noto Sans SC", "Noto Sans ", "Noto Sans Regular", "Noto Sans Bold", "Noto Sans Italic"};int i = 0;for (const auto& family : familys) {fontlist.Put(family, i++);}auto findList = fontlist.Match("Noto Sans *");for (int i = 0; i < familys.size(); i++) {if (findList[i]) {std::cout << familys[i] << std::endl;}}return 0;
}
输出

Present or Not 0
Present or Not 1
Noto Sans SC
Noto Sans
Noto Sans Regular
Noto Sans Bold
Noto Sans Italic


创作不易,小小的支持一下吧!

相关文章:

C++自定义字典树结构

代码 #include <iostream> using namespace std;class TrieNode { public:char data;TrieNode* children[26];bool isTerminal;TrieNode(char ch){data ch;for (int i 0; i < 26; i){children[i] NULL;}isTerminal false;} }; class Trie { public:TrieNode* ro…...

dockerfile部署wordpress

1.将容器直接提交成镜像 [rootlocalhost ~]# docker commit 8ecc7f6b9c12 nginx:1.1 sha256:9a2bb94ba6d8d952527df616febf3fbc8f842b3b9e28b7011b50c743cd7b233b [rootlocalhost ~]# docker images REPOSITORY TAG IMAGE ID CREATED SIZE nginx …...

CSS(二)——CSS 背景

CSS 背景 CSS 背景属性用于定义HTML元素的背景。 CSS 背景属性 Property描述background简写属性&#xff0c;作用是将背景属性设置在一个声明中。background-attachment背景图像是否固定或者随着页面的其余部分滚动。background-color设置元素的背景颜色。background-image把…...

开机出现grub无法进入系统_电脑开机出现grub解决方法

最近有小伙伴问我电脑开机出现grub无法进入系统怎么回事&#xff1f;电脑开机出grub的情况有很多&#xff0c;电脑上安装了Linux和Win10双系统&#xff0c;但是由于格式化删除了Linux之后&#xff0c;结果win10开机了之后&#xff0c;直接显示grub&#xff1e;&#xff0c;无法…...

uboot 设置bootargs配置内核网络挂载根文件系统

uboot 设置bootargs配置内核网络挂载根文件系统 uboot设置bootargs env set bootargs "mem256M consolettyAMA0,115200 root/dev/nfs init/linuxrc nfsrootnfs主机地址:nfs路径/busybox/rootfs_glibc_arm64,prototcp rw nfsvers3 rootwait ip板子地址:nfs主机地址:网关:2…...

Vue3+.NET6前后端分离式管理后台实战(三十一)

1&#xff0c;Vue3.NET6前后端分离式管理后台实战(三十一)...

22集 如何minimax密钥和groupid-《MCU嵌入式AI开发笔记》

22集 如何获取minimax密钥和groupid-《MCU嵌入式AI开发笔记》 minimax密钥获取 https://www.minimaxi.com/platform 进入minimax网站&#xff0c;注册登录后&#xff0c;进入“账户管理”&#xff0c; 然后再点击“接口密钥”&#xff0c;然后再点击“创建新的密钥”。 之…...

决策树的概念

决策树的概念 决策树是一种监督学习算法&#xff0c;主要用于分类任务。它通过构建一棵树结构模型来进行预测&#xff0c;其中每个内部节点表示一个特征属性上的判断条件&#xff0c;每条边代表一个判断结果对应的分支&#xff0c;而叶节点则代表最终的类别标签。 应用领域 …...

C++《类和对象》(中)

一、 类的默认成员函数介绍二、构造函数 构造函数名与类同名内置类型与自定义类型析构函数拷贝构造函数 C《类和对象》(中) 一、 类的默认成员函数介绍 默认成员函数就是⽤⼾没有显式实现&#xff0c;编译器会⾃动⽣成的成员函数称为默认成员函数。 那么我们主要学习的是1&…...

SpringBoot中JSR303校验

JSR是 Java EE 的一种标准&#xff0c;用于基于注解的对象数据验证。在Spring Boot应用中&#xff0c;你可以通过添加注解直接在POJO类中声明验证规则。这样可以确保在使用这些对象进行操作之前&#xff0c;它们满足业务规则。个人认为非常有用的&#xff0c;因为它减少了代码中…...

图像数据增强方法概述

图像数据增强方法概述 1. 什么是图像数据增强技术?2. 图像数据增强技术分类2.1 几何变换Python 示例代码 2.2 颜色变换2.3 噪声添加 3. 参考文献 1. 什么是图像数据增强技术? 基础概念&#xff1a;图像增强技术是计算机视觉和图像处理领域中的一个关键技术&#xff0c;主要用…...

【学习笔记】无人机系统(UAS)的连接、识别和跟踪(五)-无人机跟踪

目录 引言 5.3 无人机跟踪 5.3.1 无人机跟踪模型 5.3.2 无人机位置报告流程 5.3.3 无人机存在监测流程 引言 3GPP TS 23.256 技术规范&#xff0c;主要定义了3GPP系统对无人机&#xff08;UAV&#xff09;的连接性、身份识别、跟踪及A2X&#xff08;Aircraft-to-Everyth…...

分享从零开始学习网络设备配置--任务6.1 实现计算机的安全接入

项目描述 随着网络技术的发展和应用范围的不断扩大&#xff0c;网络已经成为人们日常生活中必不可少的一部分。园区网作为给终端用户提供网络接入和基础服务的应用环境&#xff0c;其存在的网络安全隐患不断显现出来&#xff0c;如非人为的或自然力造成的故障、事故&#xff1b…...

双向链表(C语言版)

1. 双向链表的结构 注意&#xff1a;这里的“带头”跟单链表的“头结点”是两个概念&#xff0c;实际上在单链表阶段称呼不太严谨&#xff0c;但是为了更好地理解就直接称为单链表的头结点。带头链表里的头结点&#xff0c;实际为“哨兵位”&#xff0c;哨兵位结点不存储任何有…...

【算法/学习】前缀和差分

前缀和&&差分目录 1. 前缀和的概念及作用 &#x1f308;概念 &#x1f308;用途 &#x1f319;一维前缀和 &#x1f319;二维前缀和 2. 差分的概念及用途 &#x1f308;概念&#xff1a; &#x1f308;用途 &#x1f319;一维差分 &#x1f319;二维差分 1. …...

idea Project 不显示文件和目录

idea Project 不显示文件和目录 File - Close Project - 重新打开项目即可删除.idea文件夹&#xff0c;重新打开项目即可。 原因分析: 可能与使用不同ide例如java、python打开同一项目有关 参考: https://blog.csdn.net/hgnuxc_1993/article/details/132595900 解决打开IDE…...

Linux--Socket编程预备

目录 1. 理解源 IP 地址和目的 IP 地址 2.端口号 2.1端口号(port)是传输层协议的内容 2.2端口号范围划分 2.3理解 "端口号" 和 "进程 ID" 2.4理解 socket 3.传输层的典型代表 3.1认识 TCP 协议 3.2认识 UDP 协议 4. 网络字节序 5. socket 编程接…...

100个python的基本语法知识【下】

50. 压缩文件&#xff1a; import zipfilewith zipfile.ZipFile("file.zip", "r") as zip_ref:zip_ref.extractall("extracted")51. 数据库操作&#xff1a; import sqlite3conn sqlite3.connect("my_database.db") cursor conn.c…...

Git如何将一个分支上的修改转移到另一个分支

在我们使用git进行版本控制时&#xff0c;当代码写错分支&#xff0c;怎么将这些修改转移到正确的分支上去呢&#xff1f;这时&#xff0c;我们可以使用git stath命令来暂存我们的修改&#xff0c;然后再切换到其他分支 未commit&#xff08;提交&#xff09;操作时 1. 先将修…...

jvm-证明cpu指令是乱序执行的案例

package jvm;/*** 证明cpu指令是乱序执行的** author 1* version 1.0* description: TODO* date 2024-07-19 9:31*/ public class T04_Disorder {private static int x 0, y 0;private static int a 0, b 0;public static void main(String[] args) throws InterruptedExcep…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...