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简写属性,作用是将背景属性设置在一个声明中。background-attachment背景图像是否固定或者随着页面的其余部分滚动。background-color设置元素的背景颜色。background-image把…...
开机出现grub无法进入系统_电脑开机出现grub解决方法
最近有小伙伴问我电脑开机出现grub无法进入系统怎么回事?电脑开机出grub的情况有很多,电脑上安装了Linux和Win10双系统,但是由于格式化删除了Linux之后,结果win10开机了之后,直接显示grub>,无法…...
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,Vue3.NET6前后端分离式管理后台实战(三十一)...
22集 如何minimax密钥和groupid-《MCU嵌入式AI开发笔记》
22集 如何获取minimax密钥和groupid-《MCU嵌入式AI开发笔记》 minimax密钥获取 https://www.minimaxi.com/platform 进入minimax网站,注册登录后,进入“账户管理”, 然后再点击“接口密钥”,然后再点击“创建新的密钥”。 之…...
决策树的概念
决策树的概念 决策树是一种监督学习算法,主要用于分类任务。它通过构建一棵树结构模型来进行预测,其中每个内部节点表示一个特征属性上的判断条件,每条边代表一个判断结果对应的分支,而叶节点则代表最终的类别标签。 应用领域 …...
C++《类和对象》(中)
一、 类的默认成员函数介绍二、构造函数 构造函数名与类同名内置类型与自定义类型析构函数拷贝构造函数 C《类和对象》(中) 一、 类的默认成员函数介绍 默认成员函数就是⽤⼾没有显式实现,编译器会⾃动⽣成的成员函数称为默认成员函数。 那么我们主要学习的是1&…...
SpringBoot中JSR303校验
JSR是 Java EE 的一种标准,用于基于注解的对象数据验证。在Spring Boot应用中,你可以通过添加注解直接在POJO类中声明验证规则。这样可以确保在使用这些对象进行操作之前,它们满足业务规则。个人认为非常有用的,因为它减少了代码中…...
图像数据增强方法概述
图像数据增强方法概述 1. 什么是图像数据增强技术?2. 图像数据增强技术分类2.1 几何变换Python 示例代码 2.2 颜色变换2.3 噪声添加 3. 参考文献 1. 什么是图像数据增强技术? 基础概念:图像增强技术是计算机视觉和图像处理领域中的一个关键技术,主要用…...
【学习笔记】无人机系统(UAS)的连接、识别和跟踪(五)-无人机跟踪
目录 引言 5.3 无人机跟踪 5.3.1 无人机跟踪模型 5.3.2 无人机位置报告流程 5.3.3 无人机存在监测流程 引言 3GPP TS 23.256 技术规范,主要定义了3GPP系统对无人机(UAV)的连接性、身份识别、跟踪及A2X(Aircraft-to-Everyth…...
分享从零开始学习网络设备配置--任务6.1 实现计算机的安全接入
项目描述 随着网络技术的发展和应用范围的不断扩大,网络已经成为人们日常生活中必不可少的一部分。园区网作为给终端用户提供网络接入和基础服务的应用环境,其存在的网络安全隐患不断显现出来,如非人为的或自然力造成的故障、事故;…...
双向链表(C语言版)
1. 双向链表的结构 注意:这里的“带头”跟单链表的“头结点”是两个概念,实际上在单链表阶段称呼不太严谨,但是为了更好地理解就直接称为单链表的头结点。带头链表里的头结点,实际为“哨兵位”,哨兵位结点不存储任何有…...
【算法/学习】前缀和差分
前缀和&&差分目录 1. 前缀和的概念及作用 🌈概念 🌈用途 🌙一维前缀和 🌙二维前缀和 2. 差分的概念及用途 🌈概念: 🌈用途 🌙一维差分 🌙二维差分 1. …...
idea Project 不显示文件和目录
idea Project 不显示文件和目录 File - Close Project - 重新打开项目即可删除.idea文件夹,重新打开项目即可。 原因分析: 可能与使用不同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. 压缩文件: import zipfilewith zipfile.ZipFile("file.zip", "r") as zip_ref:zip_ref.extractall("extracted")51. 数据库操作: import sqlite3conn sqlite3.connect("my_database.db") cursor conn.c…...
Git如何将一个分支上的修改转移到另一个分支
在我们使用git进行版本控制时,当代码写错分支,怎么将这些修改转移到正确的分支上去呢?这时,我们可以使用git stath命令来暂存我们的修改,然后再切换到其他分支 未commit(提交)操作时 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…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目
应用场景: 1、常规某个机器被钓鱼后门攻击后,我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后,我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...
Axure零基础跟我学:展开与收回
亲爱的小伙伴,如有帮助请订阅专栏!跟着老师每课一练,系统学习Axure交互设计课程! Axure产品经理精品视频课https://edu.csdn.net/course/detail/40420 课程主题:Axure菜单展开与收回 课程视频:...
MCP和Function Calling
MCP MCP(Model Context Protocol,模型上下文协议) ,2024年11月底,由 Anthropic 推出的一种开放标准,旨在统一大模型与外部数据源和工具之间的通信协议。MCP 的主要目的在于解决当前 AI 模型因数据孤岛限制而…...
可视化预警系统:如何实现生产风险的实时监控?
在生产环境中,风险无处不在,而传统的监控方式往往只能事后补救,难以做到提前预警。但如今,可视化预警系统正在改变这一切!它能够实时收集和分析生产数据,通过直观的图表和警报,让管理者第一时间…...
Spring Boot 与 Kafka 的深度集成实践(二)
3. 生产者实现 3.1 生产者配置 在 Spring Boot 项目中,配置 Kafka 生产者主要是配置生产者工厂(ProducerFactory)和 KafkaTemplate 。生产者工厂负责创建 Kafka 生产者实例,而 KafkaTemplate 则是用于发送消息的核心组件&#x…...
