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…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
