字典树trie详解

字典树（Trie树）实现与应⽤⼀、概述 1、基本概念 字典树，⼜称为单词查找树，Tire数，是⼀种树形结构，它是⼀种哈希树的变种。

2、基本性质根节点不包含字符，除根节点外的每⼀个⼦节点都包含⼀个字符从根节点到某⼀节点。

路径上经过的字符连接起来，就是该节点对应的字符串每个节点的所有⼦节点包含的字符都不相同 3、应⽤场景 典型应⽤是⽤于统计，排序和保存⼤量的字符串(不仅限于字符串)，经常被搜索引擎系统⽤于⽂本词频统计。

4、优点 利⽤字符串的公共前缀来减少查询时间，最⼤限度的减少⽆谓的字符串⽐较，查询效率⽐哈希树⾼。

⼆、构建过程 1、字典树节点定义class TrieNode // 字典树节点{private int num;// 有多少单词通过这个节点,即由根⾄该节点组成的字符串模式出现的次数private TrieNode[] son;// 所有的⼉⼦节点private boolean isEnd;// 是不是最后⼀个节点private char val;// 节点的值TrieNode(){num = 1;son = new TrieNode[SIZE];isEnd = false;}} 2、字典树构造函数Trie() // 初始化字典树{root = new TrieNode();} 3、建⽴字典树// 建⽴字典树public void insert(String str) // 在字典树中插⼊⼀个单词{if (str == null || str.length() == 0){return;}TrieNode node = root;char[] letters = str.toCharArray();//将⽬标单词转换为字符数组for (int i = 0, len = str.length(); i < len; i++){int pos = letters[i] - 'a';if (node.son[pos] == null) //如果当前节点的⼉⼦节点中没有该字符，则构建⼀个TrieNode并复值该字符{node.son[pos] = new TrieNode();node.son[pos].val = letters[i];}else//如果已经存在，则将由根⾄该⼉⼦节点组成的字符串模式出现的次数+1{node.son[pos].num++;}node = node.son[pos];}node.isEnd = true;} 4、在字典树中查找是否完全匹配⼀个指定的字符串// 在字典树中查找⼀个完全匹配的单词.public boolean has(String str){if(str==null||str.length()==0){return false;}TrieNode node=root;char[]letters=str.toCharArray();for(int i=0,len=str.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]!=null){node=node.son[pos];}else{return false;}}//⾛到这⼀步，表明可能完全匹配，也可能部分匹配，如果最后⼀个字符节点为末端节点，则是完全匹配，否则是部分匹配return node.isEnd;} 5、前序遍历字典树 // 前序遍历字典树.public void preTraverse(TrieNode node){if(node!=null){System.out.print(node.val+"-");for(TrieNode child:node.son){preTraverse(child);}}} 6、计算单词前缀的数量 // 计算单词前缀的数量public int countPrefix(String prefix){if(prefix==null||prefix.length()==0){return-1;}TrieNode node=root;char[]letters=prefix.toCharArray();for(int i=0,len=prefix.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]==null){return 0;}elsenode=node.son[pos];}}return node.num;} 完整代码：package com.xj.test;public class Trie{private int SIZE = 26;private TrieNode root;// 字典树的根class TrieNode // 字典树节点{private int num;// 有多少单词通过这个节点,即由根⾄该节点组成的字符串模式出现的次数private TrieNode[] son;// 所有的⼉⼦节点private boolean isEnd;// 是不是最后⼀个节点private char val;// 节点的值TrieNode(){num = 1;son = new TrieNode[SIZE];isEnd = false;}}Trie() // 初始化字典树{root = new TrieNode();}// 建⽴字典树public void insert(String str) // 在字典树中插⼊⼀个单词{if (str == null || str.length() == 0){return;}TrieNode node = root;char[] letters = str.toCharArray();//将⽬标单词转换为字符数组for (int i = 0, len = str.length(); i < len; i++){int pos = letters[i] - 'a';if (node.son[pos] == null) //如果当前节点的⼉⼦节点中没有该字符，则构建⼀个TrieNode并复值该字符 {node.son[pos] = new TrieNode();node.son[pos].val = letters[i];}else//如果已经存在，则将由根⾄该⼉⼦节点组成的字符串模式出现的次数+1{node.son[pos].num++;}node = node.son[pos];}node.isEnd = true;}// 计算单词前缀的数量public int countPrefix(String prefix){if(prefix==null||prefix.length()==0){return-1;}TrieNode node=root;char[]letters=prefix.toCharArray();for(int i=0,len=prefix.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]==null){return 0;}else{node=node.son[pos];}return node.num;}// 打印指定前缀的单词public String hasPrefix(String prefix){if (prefix == null || prefix.length() == 0){return null;}TrieNode node = root;char[] letters = prefix.toCharArray();for (int i = 0, len = prefix.length(); i < len; i++){int pos = letters[i] - 'a';if (node.son[pos] == null){return null;}else{node = node.son[pos];}}preTraverse(node, prefix);return null;}// 遍历经过此节点的单词.public void preTraverse(TrieNode node, String prefix){if (!node.isEnd){for (TrieNode child : node.son){if (child != null){preTraverse(child, prefix + child.val);}}return;}System.out.println(prefix);}// 在字典树中查找⼀个完全匹配的单词.public boolean has(String str){if(str==null||str.length()==0){return false;}TrieNode node=root;char[]letters=str.toCharArray();for(int i=0,len=str.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]!=null){node=node.son[pos];}else{return false;}}//⾛到这⼀步，表明可能完全匹配，可能部分匹配，如果最后⼀个字符节点为末端节点，则是完全匹配，否则是部分匹配return node.isEnd;}// 前序遍历字典树.public void preTraverse(TrieNode node){if(node!=null){System.out.print(node.val+"-");for(TrieNode child:node.son){preTraverse(child);}}}public TrieNode getRoot(){return this.root;}public static void main(String[]args){Trie tree=new Trie();String[]strs= {"banana","band","bee","absolute","acm",};String[]prefix= {"ba","b","band","abc",};for(String str:strs){tree.insert(str);}System.out.println(tree.has("abc"));tree.preTraverse(tree.getRoot());System.out.println();//tree.printAllWords();for(String pre:prefix){int num=tree.countPrefix(pre);System.out.println(pre+"数量:"+num);}}}View Code 执⾏结果截图：三、简单应⽤ 下⾯讲⼀个简单的应⽤，问题是这样的： 现在有⼀个英⽂字典(每个单词都是由⼩写的a-z组成)，单词量很⼤，⽽且还有很多重复的单词。

Go语⾔数据结构与算法-Trie树摘要：Trie树 概述 Trie树，⼜叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是⼀种很常⽤的树结构【多叉树】。

它被⼴泛⽤于各个⽅⾯，⽐如字符串检索、中⽂分词、求字符串最长公共前缀和字典排序等等。

核⼼思想空间换时间：数据结构本⾝⽐较消耗空间。

所有⼦节点都有⼀个共同的前缀，上图的关键字集合{"分散","分散精⼒","分散投资","分布式","⼯程","⼯程师"} 。

Trie树的基本性质：根节点是总⼊⼝，不存储字符，除根节点外的每⼀个⼦节点都包含⼀个字符。

从根节点到叶节点的完整路径是⼀个term。

从根节点到某个中间节点也可能是⼀个term，即⼀个term可能是另⼀个term的前缀。

每个节点的所有⼦节点包含的字符互不相同。

优点插⼊和查询的效率很⾼，都为，其中是待插⼊/查询的字符串的长度。

关于查询，会有⼈说 hash 表时间复杂度是不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若⼀个坏的 hash 函数导致很多的冲突，效率并不⼀定⽐Trie树⾼。

Trie树中不同的关键字不会产⽣冲突。

Trie树只有在允许⼀个关键字关联多个值的情况下才有类似hash碰撞发⽣。

Trie树不⽤求 hash 值，对短字符串有更快的速度。

通常，求hash值也是需要遍历字符串的。

Trie树可以对关键字按字典序排序。

缺点当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。

空间消耗⽐较⼤。

⽰例代码package mainimport "fmt"// Node ⼦节点type Node struct {Word rune // 当前节点存储的字符。

byte只能表⽰英⽂字符，rune可以表⽰任意字符Child map[rune]*Node // ⼦节点，⽤⼀个map存储Term string // 标记关键词}// TrieTree Trie树type TrieTree struct {root *Node}// add 把words[beginIndex:]插⼊到Trie树中func (n *Node) add(words []rune, term string, beginIndex int) {if beginIndex >= len(words) { // words已经遍历完n.Term = termreturn}if n.Child == nil {n.Child = make(map[rune]*Node)}word := words[beginIndex] // 把这个word放到node的⼦节点中if child, exists := n.Child[word]; !exists {newNode := &Node{Word: word}n.Child[word] = newNodenewNode.add(words, term, beginIndex+1) // 递归} else {child.add(words, term, beginIndex+1) // 递归}}// walk words[0]就是当前节点上存储的字符，按照words的指引顺着树往下⾛，最终返回words最后⼀个字符对应的节点func (n *Node) walk(words []rune, beginIndex int) *Node {if beginIndex == len(words)-1 {return n}beginIndex += 1word := words[beginIndex]if child, exists := n.Child[word]; exists {return child.walk(words, beginIndex)} else {return nil}}// traverseTerms 遍历⼀个node下⾯所有的term。

Trie树Trie (发音Try)，是一棵用于存储多个字符串的多叉树，由于插入和查询都极为高效，又称字典树。

树的叉数就是字符串所含的字母种数，大写字母字典树就是一棵26叉树，我们以这种Trie为例，以方便讨论。

比如要存储6个串{SHE,SHR,SAY,HE,HR,HER}Trie就是如上图所示的一棵多叉树一.Trie的结构基本的Trie的一个节点包含这么两个信息Son['A'..'Z']:Pointer {儿子指针数组,下标是字符集合}Tail:Boolean {该节点是否是一个单词的结尾}Trie的字符信息纪录在边(指针)上,节点保存一些附加信息一般Trie的空间占用比较大与字符总数成正比。

(鉴于Pascal的指针很鸡肋下文一般用数组模拟指针)二.Trie的插入(建树)总结起来就是边读边走边插入首先让当前指针P指向Root (预处理时注意新建Root)，接下来每读入一个字符判断当前节点是否有这样一个儿子，如果没有实时新建，判断完后然后继续往这个儿子走，即P=Son[Ch]读完一个串，最后一个节点的Tail记为True表示是词尾。

给出Trie插入的代码: Trie_Buildnewnode(root);readln(n);for i:=1to n dobeginp:=root;while not eoln dobeginread(ch);c:=ord(ch)-96;if s[p][c]=0then newnode(s[p][c]);p:=s[p][c];end;inc(g[p]);readln;end;三.Trie的查询查询就是边读边走不插入, 每读入一个字符判断有没有所需的儿子没有就代表查询失败; 如果读到完, 最后的节点不是词尾(根据Tail 判断) 也是查询失败。

代码和查询类似四.总结Trie的插入和查询时间复杂度都是线性的O(Length)但是空间复杂度达到了O(K*Length) 或O(∑Length)针对这个问题可以采取压缩Trie来解决使空间复杂度达到O(K)这个方法我还不会也没有碰到要用的地方最后给出一个用来测试Trie的问题/problem?id=3630Phone ListTime Limit: 1000MS Memory Limit: 65536K DescriptionGiven a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers: ∙Emergency 911∙Alice 97 625 999∙Bob 91 12 54 26In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.InputThe first line of input gives a single integer, 1 ≤ t≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.OutputFor each test case, output "YES" if the list is consistent, or "NO" otherwise.Sample Input2391197625999911254265113123401234401234598346Sample OutputNOYES最简单Trie代码就可以解决了const maxc=10;maxn=500000;var t:array[1..maxn]of longint;n:array[1..maxn,1..maxc]of longint;tt,ca,m,i,p,k,root:longint;flag,bool:boolean;ch:char;procedure NewNode(var x:longint);var i:longint;begininc(tt); x:=tt;t[x]:=0;for i:=1to maxc don[x][i]:=0;end;beginassign(input,'PList.in'); reset(input);assign(output,'PList2.out'); rewrite(output); readln(ca);while ca>0dobegintt:=0;dec(ca);readln(m);NewNode(root);flag:=true;for i:=1to m dobeginp:=root;bool:=true;while not eoln dobeginread(ch);k:=ord(ch)-47;if n[p][k]=0then beginNewNode(n[p][k]);bool:=false;end;p:=n[p][k];if t[p]>0then flag:=false;end;if bool=true then flag:=false; inc(t[p]);readln;end;if flagthen writeln('YES')else writeln('NO');end;close(input); close(output);end.。

基数树查找原理
基数树（Radix Tree），也称为字典树（Trie），是一种常用于高效存储和检索字符串的数据结构。

它的设计理念是基于字符串的特性，将字符串的每个字符作为节点进行存储和检索。

基数树的查找原理是通过将要存储或检索的字符串拆分为单个字符，并将每个字符作为节点插入到树中。

树的根节点代表空字符，每个节点包含一个字符和一个指向子节点的指针数组。

在进行插入操作时，将要插入的字符串从左到右逐个字符地与树中的节点进行比较。

若节点为空，则创建一个新节点并连接到父节点的对应子节点指针上；若节点不为空，则继续比较下一个字符。

插入完成后，将字符串的最后一个字符所对应的节点标记为终止节点，表示该字符串的结束。

在进行查找操作时，同样从根节点开始，逐个字符与节点进行比较。

若节点为空，则表示该字符串不存在于树中，查找失败；若节点不为空，则继续比较下一个字符。

当达到字符串的最后一个字符时，如果对应的节点为终止节点，则表示该字符串存在于树中，查找成功；否则查找失败。

基数树的优势是在存储和检索字符串时具有较高的效率。

由于它的特性是按照字符进行存储和检索，所以对于相同前缀的字符串，它们共享相同的前缀节点，节省了空间。

同时，基数树也支持高效的前缀匹配，可以快速地找到具有相同前缀的字符串。

总结起来，基数树是一种通过将字符串拆分为单个字符并按照字符序列构建树的数据结构。

它的查找原理是通过比较字符串的每个字符与树中的节点进行匹配，直到字符串结束或遇到终止节点。

基数树在存储和检索字符串方面具有高效性和前缀匹配的优势。

Trie树Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。

一.Trie树的原理利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。

下面以英文单词构建的字典树为例，这棵Trie树中每个结点包括26个孩子结点，因为总共有26个英文字母(假设单词都是小写字母组成)。

则可声明包含Trie树的结点信息的结构体:const int MAX=26struct TrieNode //Trie结点声明{bool isStr; //标记该结点处是否构成单词TrieNode *next[MAX]; //儿子分支}Trie;其中next是一个指针数组，存放着指向各个孩子结点的指针。

如给出字符串"abc","ab","bd","dda"，根据该字符串序列构建一棵Trie树。

则构建的树如下:Trie树的根结点不包含任何信息，第一个字符串为"abc"，第一个字母为'a'，因此根结点中数组next 下标为'a'-97的值不为NULL，其他同理，构建的Trie树如图所示，红色结点表示在该处可以构成一个单词。

很显然，如果要查找单词"abc"是否存在，查找长度则为O(len)，len为要查找的字符串的长度。

而若采用一般的逐个匹配查找，则查找长度为O(len*n)，n为字符串的个数。

显然基于Trie 树的查找效率要高很多。

但是却是以空间为代价的，比如图中每个结点所占的空间都为(26*4+1)Byte=105Byte，那么这棵Trie树所占的空间则为105*8Byte=840Byte，而普通的逐个查找所占空间只需(3+2+2+3)Byte=10Byte。

二.Trie树的操作在Trie树中主要有3个操作，插入、查找和删除。

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

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。

利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3.每个节点的所有子节点包含的字符都不相同。

1.2、树的构建举个在网上流传颇广的例子，如下：题目：给你100000个长度不超过10的单词。

对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。

分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。

比如说对于某一个单词，我们要询问它的前缀是否出现过。

这样hash就不好搞了，而用trie还是很简单。

现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。

那么这个算法的复杂度就是O(n^2)。

显然对于100000的范围难以接受。

现在我们换个思路想。

假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。

而只要找以a开头的中是否存在abcd就可以了。

同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。

好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词，我们构建的树就是如下图这样的：当时第一次看到这幅图的时候，便立马感到此树之不凡构造了。

单单从上幅图便可窥知一二，好比大海搜人，立马就能确定东南西北中的到底哪个方位，如此迅速缩小查找的范围和提高查找的针对性，不失为一创举。

Trie树高效存储与搜索字符串的数据结构Trie树是一种高效存储和搜索字符串的数据结构。

它是由Edward Fredkin于1960年提出的，并在计算机科学领域得到广泛应用。

Trie树，也称为字典树或前缀树，是一种树形结构，用于存储字符串的集合。

与传统的二叉搜索树不同，Trie树的每个节点可能有多个子节点，每个子节点代表一个字符。

通过从根节点到某个叶子节点的路径，可以唯一确定一个字符串。

这使得Trie树非常适合存储和搜索字符串。

下面是Trie树的结构示意图：```root/ | \t a b/ | \o n y| / \ | \p r d e a| | | | |e y g r t| | | | |n e g e|r```在上面的示例中，我们可以从根节点到叶子节点沿路径"t -> a -> b -> o -> n -> e -> y"找到单词"taboney"。

这种存储方式使得在Trie树中搜索、插入和删除字符串的操作非常高效。

Trie树的搜索操作是通过从根节点开始，逐个比较目标字符串的字符来实现的。

如果字符存在于当前节点的子节点中，则继续向下遍历。

一旦没有子节点与目标字符匹配，或者目标字符串已经遍历完，则搜索操作结束。

如果最后一个字符所在的节点为叶子节点，则表示目标字符串在Trie树中存在。

下面是Trie树的搜索操作示例：```pythonclass TrieNode:def __init__(self):self.children = [None] * 26self.is_end_of_word = Falseclass Trie:def __init__(self):self.root = TrieNode()def insert(self, word):current = self.rootfor ch in word:index = ord(ch) - ord('a')if not current.children[index]:current.children[index] = TrieNode() current = current.children[index]current.is_end_of_word = Truedef search(self, word):current = self.rootfor ch in word:index = ord(ch) - ord('a')if not current.children[index]:return Falsecurrent = current.children[index]return current.is_end_of_word```使用上述代码，我们可以创建一个Trie对象，并使用insert函数插入字符串。

trie字典树总结-回复什么是trie字典树？Trie字典树，也称为前缀树，是一种特殊的树形数据结构，用于存储和检索键-值对。

它的特点是使用字符串中的字符作为节点进行构建，键的相同前缀被合并为一个子树，从而实现快速的字符串检索。

trie字典树是一种高效的数据结构，特别适用于处理大量字符串的场景，如搜索引擎、计算机网络和编译器等。

trie字典树的特点是什么？1. 前缀共享：trie字典树能够有效地利用字符串键的前缀共享。

例如，假设要存储"apple"、"app"和"application"这三个键，它们的前缀"app"会在trie中被合并为一个子树，从而节省了空间。

2. 快速查找：利用trie字典树，我们可以在O(m)的时间复杂度下（其中m是键的长度）查找到指定的字符串。

trie字典树将键分布在树中，每个字符都是树的一个节点，通过将输入字符串的字符一个一个地与树的节点进行匹配，最终找到完整的键。

3. 空间效率：尽管trie字典树可能需要较多的内存来存储节点，但它可以大大减少存储重复前缀带来的额外开销。

对于字符串数量较多或重复前缀较长的数据集，trie字典树可以更好地利用内存空间。

trie字典树的基本结构是什么？trie字典树由多个节点组成，每个节点包含一个字符和若干指向子节点的指针。

通常，根节点不包含字符，其他节点分别表示某个字符。

每个节点还存储一个布尔值，表示当前节点是否为某个字符串的结尾。

trie字典树的节点可能有多个子节点，取决于输入字符串的不同字符数。

对于小写英文字母，一个节点最多有26个子节点。

这种结构使得trie字典树可以有效地处理大量的字符串。

trie字典树的构建过程是怎样的？1. 创建根节点：首先，我们需要创建一棵空的trie字典树，只包含一个根节点。

根节点不包含字符，即为空。

2. 插入键值对：对于要插入的每个键值对，我们从根节点开始，按照键中的字符顺序依次遍历trie树。

trie字典树模板浅析什么是trie？百度百科⼜称单词查找树，Trie树，是⼀种树形结构，是⼀种哈希树的变种。

典型应⽤是⽤于统计，排序和保存⼤量的字符串（但不仅限于字符串），所以经常被搜索引擎系统⽤于⽂本词频统计。

它的优点是：利⽤字符串的公共前缀来减少查询时间，最⼤限度地减少⽆谓的字符串⽐较，查询效率⽐哈希树⾼。

trie有什么⽤处？①进⾏快速的查找字符串是否存在②进⾏快速的字符串的前缀和的相关的性质的查询如何实现trie？导⾔trie是靠⼆维数组进⾏存储的，其中trie[a][b]=c，指的是a的第b个孩⼦的编号是c。

特别的trie是⽤边来存储字符⽽并不是节点！编号代表的是a-z的26个字母中的第⼏个字母所以编号是从0-25。

百度百科的图⽚①insert函数insert函数代表着插⼊操作。

如何实现呢？(1)把需要插⼊的string拆分成⼀个⼜⼀个的单个的字符进⾏操作。

并且把rt初始化为0int rt=0;for(int i=0;i<a.size();i++){//....}(2)计算id编号(注意这个地⽅是-'a'不是-'0')int id=a[i]-'a';(3)循环判断当前的⽗节点是不是存在⼀条以id编号的边，如果不存在那么，添加⼀个这样的边并且把⼦节点赋予⼀个编号if(!trie[rt][id])trie[rt][id]=++tot;(4)将rt层层递进rt=trie[rt][id];insert函数完整代码void insert(string a){int rt=0;for(int i=0;i<a.size();i++){int id=a[i]-'a';if(!trie[rt][id])trie[rt][id]=++tot;rt=trie[rt][id];}}②search函数search函数代表着查询的操作，这⾥我们查询当前前缀是不是在树中，当然trie可以做很多别的操作，结合insert函数，如何实现？(1)(2)同insert函数int rt=0;for(int i=0;i<a.size();i++){int id=a[i]-'a';//.....}(3)查询相应的编号的边是不是这个⽗节点的⼉⼦，如果不是那么返回0if(!trie[rt][id])return 0;(4)层层递进同insertrt=trie[rt][id];(5)如果这个字符串能安全的⾛出循环，那么就返回1，说明这个前缀是存在的search函数完整代码int search(string a){int rt=0;for(int i=0;i<a.size();i++){int id=a[i]-'a';if(!trie[rt][id])return 0;rt=trie[rt][id];}return 1;}trie模板完整代码(注意此处的map效率过慢，应该直接开数组为妙)#include <bits/stdc++.h>using namespace std;map<int,map<int,int> > trie;map<int,int> sum;int tot;void insert(string a){int rt=0;for(int i=0;i<a.size();i++){int id=a[i]-'a';if(!trie[rt][id])trie[rt][id]=++tot;rt=trie[rt][id];}}int search(string a){int rt=0;for(int i=0;i<a.size();i++){int id=a[i]-'a';if(!trie[rt][id])return 0;rt=trie[rt][id];}return 1;}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;for(int i=0;i<n;i++){string a;cin>>a;insert(a);}for(int i=0;i<m;i++){string a;cin>>a;if(search(a))cout<<"YES\n";elsecout<<"NO\n";}}拓展①查询相应前缀所包含的字符串的数量(hdu 1251 统计难题)只需要在insert函数中设定⼀个sum数组，保存每个节点遍历过的次数，即sum[trie[rt][id]]++，然后在search函数中寻找到字符串最后的节点返回sum[rt]即可。