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…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...

springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
背包问题双雄:01 背包与完全背包详解(Java 实现)
一、背包问题概述 背包问题是动态规划领域的经典问题,其核心在于如何在有限容量的背包中选择物品,使得总价值最大化。根据物品选择规则的不同,主要分为两类: 01 背包:每件物品最多选 1 次(选或不选&#…...
基于Uniapp的HarmonyOS 5.0体育应用开发攻略
一、技术架构设计 1.混合开发框架选型 (1)使用Uniapp 3.8版本支持ArkTS编译 (2)通过uni-harmony插件调用原生能力 (3)分层架构设计: graph TDA[UI层] -->|Vue语法| B(Uniapp框架)B --&g…...