数据结构---字典树(Tire)

字典树是一种能够快速插入和查询字符串的多叉树结构,节点的编号各不相同,根节点编号为0

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。

核心思想也是通过空间来换取时间上的效率

在一定情况下字典树的效率要比哈希表要高

字典树在解决公共前缀的使用,所以叫前缀树

 先说如何创建字典树

这个是只有26个小写字母存放的字典树

class TrieNode{
public:TrieNode* next[26];bool isword;TrieNode(){memset(next,NULL,sizeof(next));isword=false;}~TrieNode(){for(int i=0;i<26;i++)if(next[i])delete next[i];}
};

也可以直接用c++中的特殊的数据结构来实现

struct Node {unordered_map<int, Node*> son;int cnt = 0;
};

但是在下面必须要对根节点进行补充,根节点为空

Node *root = new Node();

leetcode3043. 最长公共前缀的长度-CSDN博客

leetcode3042. 统计前后缀下标对 I-CSDN博客

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

这道题之前用的暴力去模拟这个过程,效率太低,,采用前缀树来解决

class Solution {
public:long long countPrefixSuffixPairs(vector<string>& words) {long long cnt=0;int i,j;for(i=0;i<words.size()-1;i++){for(j=i+1;j<words.size();j++){if(words[j].find(words[i])==0 && words[j].rfind(words[i])==words[j].length()-words[i].length()){cnt++;}}}return cnt;}
};

但是前缀树解决的是前缀的问题,这道题让解决的是前缀和后缀的问题,所以想要把这个字符串转变一下来解决,

【1】首先我先到的是建造两个前缀树,一个正向前缀树,一个反向前缀树

 【2】可以用一个pair去储存步骤1的过程

正 ab                   abcdab

反 ba                   badcba

[(a,b),(b,a)]             [(a,b),(b,a),.....]

由此可见如果是前后缀的话,应该会在pair列表中出现

class Node:__slots__ = 'son', 'cnt'def __init__(self):self.son = dict()self.cnt = 0class Solution:def countPrefixSuffixPairs(self, words: List[str]) -> int:ans = 0root = Node()for t in words:z = self.calc_z(t)cur = rootfor i, c in enumerate(t):if c not in cur.son:cur.son[c] = Node()cur = cur.son[c]if z[-1 - i] == i + 1:  # t[-1-i:] == t[:i+1]ans += cur.cntcur.cnt += 1return ansdef calc_z(self, s: str) -> List[int]:n = len(s)z = [0] * nl, r = 0, 0for i in range(1, n):if i <= r:z[i] = min(z[i - l], r - i + 1)while i + z[i] < n and s[z[i]] == s[i + z[i]]:l, r = i, i + z[i]z[i] += 1z[0] = nreturn z

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/260501.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Kotlin】Kotlin流程控制

1 选择结构 Kotlin 中选择结构主要包含 if -else、when 语句&#xff0c;并且可以返回结果。 1.1 if-else 1.1. 条件选择 fun main() {var score 85if (score > 90) {println("优秀")} else if (score > 80) {println("良好")} else if (score &…

Linux---守护进程

运行的这个进程&#xff0c;它的pid和gpid(进程组ID)一样&#xff0c;它是自成一组的。 这就是一个进程组。 进程组和任务有什么关系&#xff1f; 将任务指派给进程组。任务都是由进程组去完成的。 可以发现&#xff0c;这三个进程的会话id1351都是一样的&#xff0c;多个任…

动态内存管理(中)

动态内存管理&#xff08;上&#xff09;-CSDN博客&#xff08;malloc&#xff0c; realloc&#xff0c; calloc&#xff0c; free函数的用法以及注意事项等知识点&#xff09; 目录 1.对空指针的解引用操作 2.对动态开辟空间的越界访问 3.对非动态内存开辟空间使用free空间…

服务器遭受 DDoS 攻击的常见迹象有哪些?

服务器遭受 DDoS 攻击的现象很常见&#xff0c;并且有时不容易预防&#xff0c;有部分原因是它们的形式多种多样&#xff0c;而且黑客手段越来越隐蔽。如果您怀疑自己可能遭受 DDoS 攻击&#xff0c;可以寻找多种迹象。以下是 DDoS 攻击的5个常见迹象&#xff1a; 1.网络流量无…

力扣OJ题——相交链表

题目&#xff1a;160. 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 思路一&#xff08;暴力求解&#xff09;&#xff1a; A链表的每个节点依次跟B链表中节点进行…

python-pyqt5-工具按钮(QToolButton)添加菜单(QMenu)

QToolButton提供了比普通按钮更丰富的功能。它可以显示一个图标、一个文本或二者结合&#xff0c;还支持各种样式和行为&#xff0c;例如弹出菜单或多种动作模式 样式 setToolButtonStyle(Qt.ToolButtonStyle) # 设置按钮样式风格# 参数Qt.ToolButtonIconOnly …

芋道-------如何实现工作流退回后重新提交到之前退回的节点

一、概述 上一节&#xff0c;我们讲过了工作流如何退回到申请人&#xff0c;接下来我们来讲一讲&#xff0c;如何重新提交。这里重新提交可以是再走一遍正常流程&#xff0c;同时也可以是直接跳过中间的步骤&#xff0c;直接继续给上一步退回的人审批。文章中会提及这两种情况。…

全面解读视频生成模型Sora

2024年2月15日&#xff0c;OpenAI在其官网发布了《Video generation models as world simulators》的报告&#xff0c;该报告提出了作为世界模拟器的视频生成模型Sora。 OpenAI对Sora介绍如下&#xff1a; We explore large-scale training of generative models on video dat…

echarts制作两个柱状图

let colorList[#02ce8b,#ffbe62,#f17373]; let data1 [90,80,70,50] option { title:[{ // 第一个标题text: 环保检测, // 主标题textStyle: { // 主标题样式color: #333,fontWeight: bold,fontSize: 16},left: 20%, // 定位到适合的位置top: 10%, // 定位到适合的位置},{ //…

【Redis】理论进阶篇------Redis的持久化

一、前言 前面学习了Redis的相关的十大数据类型以及用SpringBoot集成我们的Redis的工具代码的书写。从这篇文章开始&#xff0c;就会从Redis相关的一些理论&#xff08;也是面试和工作的热点知识&#xff09;如&#xff1a;Redis的持久化、Redis的订阅发布模型、Redis集群环境搭…

wayland(xdg_wm_base) + egl + opengles 纹理贴图进阶实例(四)

文章目录 前言一、使用gstreamer 获取 pattern 图片二、代码实例1. pattern 图片作为纹理数据源的代码实例1.1 基于opengles2.0 接口的 egl_wayland_texture2_1.c1.2 基于opengles3.0 接口的 egl_wayland_texture3_1.c2. xdg-shell-client-protocol.h 和 xdg-shell-protocol.c3…

【C/C++】实现Reactor高并发服务器 完整版

代码结构 文件介绍 InetAddress.h InetAddress类 ip和端口设置 Socket.h Socket类 设置fd Epoll.h epollfd 管理类 Channel.h Channel类 管理epoll以及对应回调函数实现 EventLoop.h EventLoop事件循环类 TcpServer.h 服务器类 tcpepoll.cpp 主函数 InetAddress.h #if…

阿里云服务器被攻击黑洞了怎么办?

今天一个用户使用阿里云服务器遭受DDOS攻击&#xff0c;收到了攻击的提醒短信&#xff0c;服务器也进入黑洞&#xff0c;联系到了德迅云安全&#xff0c;询问有什么解决办法。目前网络攻击事件频发&#xff0c;相信不少用户都曾收到过类似的攻击短信。今天德迅云安全就分享下&a…

模板(函数模板)---C++

模板目录 模板1.模板概念&#xff12;.泛型编程 1.函数模板1.1 函数模板语法1.2 函数模板注意事项1.3 普通函数与函数模板的区别1.4 普通函数与函数模板的调用规则1.5 模板的局限性1.6 函数模板案例 模板 1.模板概念 模板就是建立通用的模具&#xff0c;大大提高复用性。 模板…

Leetcoder Day16| 二叉树 part05

语言&#xff1a;Java/C 513.找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1示例 2: 输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7 本题需要满足两…

3个密码学相关的问题

一、离散对数问题&#xff08;Discrete Logarithm Problem, DLP&#xff09; 问题描述&#xff1a;给定 有限阿贝尓群 G中的2个元素a和b&#xff0c;找出最小的正整数x满足&#xff1a;b a ^^ x &#xff08;或者证明这样的x不存在&#xff09;。 二、阶数问题&#xff08;O…

【STM32】硬件SPI读写W25Q64芯片

目录 基础知识回顾&#xff1a; SPI外设简介 SPI框图 主模式全双工连续传输 非连续传输 初始化SPI外设 核心代码 - 交换一个字节 硬件接线图 Code 程序配置过程 MySPI.c MySPI.h W25Q64.c W25Q64.h W25Q64_Ins.h main.c 基础知识回顾&#xff1a; 【STM32】SP…

【压缩感知基础】Nyquist采样定理

Nyquist定理&#xff0c;也被称作Nyquist采样定理&#xff0c;是由哈里奈奎斯特在1928年提出的&#xff0c;它是信号处理领域的一个重要基础定理。它描述了连续信号被离散化为数字信号时&#xff0c;采样的要求以避免失真。 数学表示 Nyquist定理的核心内容可以描述如下&…

命令执行讲解和函数

命令执行漏洞简介 命令执行漏洞产生原因 应用未对用户输入做严格得检查过滤&#xff0c;导致用户输入得参数被当成命令来执行 命令执行漏洞的危害 1.继承Web服务程序的权限去执行系统命会或读写文件 2.反弹shell&#xff0c;获得目标服务器的权限 3.进一步内网渗透 远程代…

自己动手写编译器:使用 PDA 实现增强和属性语法的解析

在前面章节中我们了解了增强语法和属性语法&#xff0c;特别是看到了这两种语法的结合体&#xff0c;本节我们看看如何使用前面我们说过的自顶向下自动机来实现这两种语法结合体的解析&#xff0c;这里使用的方法也是成熟编译器常用的一种语法解析算法。 首先我们先给出上一节…