最近很多小伙伴都在问在基数树/patriciatrie中搜索前缀和写出下列基数词的序数词这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展014-数据结构-树形结构-基数树、Patr

最近很多小伙伴都在问在基数树/ patricia trie中搜索前缀和写出下列基数词的序数词这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展014 - 数据结构 - 树形结构 - 基数树、Patricia 树、默克尔树、梅克尔帕特里夏树 (Merkle Patricia Tree, MPT)、208-实现 Trie (前缀树)、745. 前缀和后缀搜索 : 常规 Trie 运用题、algorithm – 在ORACLE中搜索最长前缀的最快方法等相关知识，下面开始了哦！

• 在基数树/ patricia trie中搜索前缀（写出下列基数词的序数词）
• 014 - 数据结构 - 树形结构 - 基数树、Patricia 树、默克尔树、梅克尔帕特里夏树 (Merkle Patricia Tree, MPT)
• 208-实现 Trie (前缀树)
• 745. 前缀和后缀搜索 : 常规 Trie 运用题
• algorithm – 在ORACLE中搜索最长前缀的最快方法

在基数树/ patricia trie中搜索前缀（写出下列基数词的序数词）

我目前正在实现基数树/ patricia
trie（无论您想称呼它如何）。我想将其用于在功能严重不足的硬件上的字典中的前缀搜索。它应该或多或少像自动完成一样工作，即显示键入的前缀匹配的单词列表。

我的实现基于本文，但是其中的代码不包括前缀搜索，尽管作者说：

[…]假设您要枚举具有公共前缀为“ AB”的键的所有节点。您可以从该根开始执行深度优先搜索，每当遇到后边缘时便停止搜索。

但是我不知道这应该如何工作。例如，如果我从这些词构建基数树：

疾病
虚构
想象
想象
模仿
立即
立即
巨大
的

我将获得与前缀“ i”和“ in”完全相同的“最佳匹配”，因此我似乎很难仅通过从最佳匹配中遍历树来收集所有匹配单词。

此外，Java中有一个基数树实现，在RadixTreeImpl.java中具有已实现的前缀搜索。该代码显式检查所有节点（从某个节点开始）是否存在前缀匹配-
它实际上比较字节。

谁能指出我对在基数树上执行前缀搜索的详细说明？Java实现中使用的算法是唯一的方法吗？

答案1

考虑一下您的特里编码。在每个节点上，都有通往该节点的路径，因此，在您的示例中，从与空字符串相对应的根节点Λ（这是大写的Lambda，这种希腊字体很烂）开始。Λ每个使用的字母都有孩子，因此在您的数据集中，您有一个分支“
i”。

• Λ
• Λ→“ i”

在“ i”节点上，有两个孩子，一个用于“ m”，一个用于“ n”。下一个字母是“ n”，所以你接受了

• Λ→“ i”→“ n”

并且由于数据集中唯一以“ i”，“ n”开头的单词 是 “ in”，因此“ n”中没有子代。那是一场比赛。

现在，假设数据集具有“ infindibulum”，而不是“ in”。（我要参考的SF仍作为练习。）您仍然会以相同的方式到达“
n”节点，但是如果下一个字母是“ q”，则知道单词不会出现在您的数据集中根本没有，因为没有“
q”分支。那时，您说“好，不匹配”。（也许您然后开始添加单词，也许不是，取决于应用程序。）

但是，如果下一个字母是“ f”，则可以继续。不过，您可以通过一些技巧来实现以下目的：到达代表唯一路径的节点后，就可以将 整个字符串
挂在该节点上。当到达该节点时，您知道字符串的其余部分 必须 是“ findibulum”，因此您已使用前缀来匹配整个字符串，然后将其返回。

您如何使用它？在许多非UNIX命令解释器中，例如旧的VAX DCL，您可以使用命令的任何唯一前缀。因此， ls（1）
的等效项是DIRECTORY，但是没有其他命令以DIR开头，因此您可以键入DIR，这与完成整个单词一样好。如果您不记得正确的命令，则可以只键入“
D”，然后按（我认为）ESC；DCL CLI会返回以开头的 所有 命令，D搜索速度可能非常快。

014 - 数据结构 - 树形结构 - 基数树、Patricia 树、默克尔树、梅克尔帕特里夏树 (Merkle Patricia Tree, MPT)

一、基数树

　　Radix 树，即基数树，也称压缩前缀树，是一种提供 key-value 存储查找的数据结构。与 Trie 不同的是，它对 Trie 树进行了空间优化，只有一个子节点的中间节点将被压缩。同样的，Radix 树的插入、查询、删除操作的时间复杂度都为 O (k)。

1.1、Radix 树特点

　　一般由根节点、中间节点和叶子节点组成。
　　每个节点可以包含一个或多个字符。
　　树的叶子结点数即是数据条目数。
　　从根节点到某一节点经过路径的字符连起来即为该节点对应的字符串。
　　每个节点的所有子节点字符串都不相同。

1.2、说明

　　对于长整型数据的映射。怎样解决 Hash 冲突和 Hash 表大小的设计是一个非常头疼的问题。

　　radix 树就是针对这样的稀疏的长整型数据查找，能高速且节省空间地完毕映射。借助于 Radix 树，我们能够实现对于长整型数据类型的路由。　　

　　利用 radix 树能够依据一个长整型（比方一个长 ID）高速查找到其相应的对象指针。这比用 hash 映射来的简单，也更节省空间，使用 hash 映射 hash 函数难以设计，不恰当的 hash 函数可能增大冲突，或浪费空间。

　　radix tree 是一种多叉搜索树。树的叶子结点是实际的数据条目。每一个结点有一个固定的、2^n 指针指向子结点（每一个指针称为槽 slot，n 为划分的基的大小）

1.3、Radix 树在 Linux 中的应用：

　　Linux 基数树（radix tree）是将 long 整数键值与指针相关联的机制，它存储有效率。而且可高速查询，用于整数值与指针的映射（如：IDR 机制）、内存管理等。

1.4、基数树的缺点:

　　基数树另一个主要的缺陷是低效。即使你只想存一个键值对，但其中的键长度有几百字符长，那么每个字符的那个层级你都需要大量的额外空间。每次查找和删除都会有上百个步骤。在这里我们引入 Patricia 树来解决这个问题。

二、Patricia 树

　　Patricia 树，或称 Patricia trie，或 crit bit tree，压缩前缀树，是一种更节省空间的 Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。

三、Merkle 树

　　Merkle Tree，通常也被称作 Hash Tree，顾名思义，就是存储 hash 值的一棵树。Merkle 树的叶子是数据块 (例如，文件或者文件的集合) 的 hash 值。非叶节点是其对应子节点串联字符串的 hash。

　　Merkle Tree 由 Hash List 演化而来：在点对点网络中作数据传输的时候，会同时从多个机器上下载数据，而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性，更好的办法是把大的文件分割成小的数据块（例如，把分割成 2K 为单位的数据块）。这样的好处是，如果小块数据在传输过程中损坏了，那么只要重新下载这一快数据就行了，不用重新下载整个文件。

　　怎么确定小的数据块没有损坏哪？只需要为每个数据块做 Hash。BT 下载的时候，在下载到真正数据之前，我们会先下载一个 Hash 列表。那么问题又来了，怎么确定这个 Hash 列表本身是正确的哪？答案是把每个小块数据的 Hash 值拼到一起，然后对这个长字符串在作一次 Hash 运算，这样就得到 Hash 列表的根 Hash (Top Hash or Root Hash)。下载数据的时候，首先从可信的数据源得到正确的根 Hash，就可以用它来校验 Hash 列表了，然后通过校验后的 Hash 列表校验数据块。

　　Merkle Tree 可以看做 Hash List 的泛化（Hash List 可以看作一种特殊的 Merkle Tree，即树高为 2 的多叉 Merkle Tree。

　　在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个” 子哈希 “。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。

　　在 p2p 网络下载网络之前，先从可信的源获得文件的 Merkle Tree 树根。一旦获得了树根，就可以从其他从不可信的源获取 Merkle tree。通过可信的树根来检查接受到的 MerkleTree。如果 Merkle Tree 是损坏的或者虚假的，就从其他源获得另一个 Merkle Tree，直到获得一个与可信树根匹配的 MerkleTree。

　　Merkle Tree 和 HashList 的主要区别是，可以直接下载并立即验证 Merkle Tree 的一个分支。因为可以将文件切分成小的数据块，这样如果有一块数据损坏，仅仅重新下载这个数据块就行了。如果文件非常大，那么 Merkle tree 和 Hash list 都很到，但是 Merkle tree 可以一次下载一个分支，然后立即验证这个分支，如果分支验证通过，就可以下载数据了。而 Hash list 只有下载整个 hash list 才能验证。

四、MPT (Merkle Patricia Tree) 树

　　MPT（Merkle Patricia Tree）就是这两者混合的数据结构。　　

　　Merkle Patricia Tree，梅克尔帕特里夏树，提供了一个基于加密学的，自校验防篡改的数据结构，用来存储键值对关系。后文中将简称为 MPT。尽管在本规范范围内，我们限定键值的类型只能是字符串（但仍对所有的类型适用，因为只需提供一个简单的序列化和反序化机制，将要存储的类型与字符串进行转换即可）。

　　MPT 是确定的。确定性是指同样内容的键值，将被保证找到同样的结果，有同样的根哈希。关于效率方面，对树的插入，查找，删除的时间复杂度控制在 O(log(n))。相较于红黑树来说，MPT 更好理解和编码实现。

　　MPT 树中的节点包括空节点、叶子节点、扩展节点和分支节点:

　　　　空节点，简单的表示空，在代码中是一个空串。

　　　　叶子节点（leaf），表示为 [key,value] 的一个键值对，其中 key 是 key 的一种特殊十六进制编码，value 是 value 的 RLP 编码。

　　　　扩展节点（extension），也是 [key，value] 的一个键值对，但是这里的 value 是其他节点的 hash 值，这个 hash 可以被用来查询数据库中的节点。也就是说通过 hash 链接到其他节点。

　　　　分支节点（branch），因为 MPT 树中的 key 被编码成一种特殊的 16 进制的表示，再加上最后的 value，所以分支节点是一个长度为 17 的 list，前 16 个元素对应着 key 中的 16 个可能的十六进制字符，如果有一个 [key,value] 对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。

　　MPT 树中另一个重要的概念是十六进制前缀 (hex-prefix, HP) 编码，用来对 key 进行编码。因为字母表是 16 进制的，所以每个节点可能有 16 个孩子。因为有两种 [key,value] 节点 (叶节点和扩展节点)，引进一种特殊的终止符标识来标识 key 所对应的是值是真实的值，还是其他节点的 hash。如果终止符标记被打开，那么 key 对应的是叶节点，对应的值是真实的 value。如果终止符标记被关闭，那么值就是用于在数据块中查询对应的节点的 hash。

参看地址：https://blog.csdn.net/smilejiasmile/article/details/82843278#_169 

208-实现 Trie (前缀树)

前言

前缀树是一种很常用的数据结构，例如我们常用的数据库索引。而关于前缀树的介绍，由于LeetCode中国有关于前缀树的教程，我就不班门弄斧了，我的答案也是参考教程的思路去解答，希望可以给大家一个参考。下面是原题目：

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

解题思路

1. 树是由节点组成，节点定义应该包含节点值(前缀树的定义，值应该为一个字符char)和叶子节点的指针，但是为了识别是否为一个单词的最后一个字符，所以增加一个boolean变量识别。
2. 由于已知输入为全小写(a-z)的字母，所以可以使用一个长度为26的数组存储叶子节点。且由于a-z的ASCII码是连续的，其ASCII是从97-123，所以可以直接使用 ASCII码-97=对应节点的数组下标。

基于数组实现的前缀树

class Trie {
    /**
     * 当前节点的值
     */
    public char value;
    /**
     * a-z有26个字母，需要访问时由于a的ASCII码为97，所以所有字母访问的对应下表皆为 字母的ASCII码-97
     */
    public Trie[] children=new Trie[26];
    /**
     * 标识此节点是否为某个单词的结束节点
     */
    public boolean endAsWord=false;
    
    public Trie() {
        
    }
    /**
     * 插入一个单词
     * @param word 单词
     */
    public void insert(String word) {
        if(word!=null){
            //分解成字符数组
            char[] charArr=word.toCharArray();
            //模拟指针操作,记录当前访问到的树的节点
            Trie currentNode=this;
            for(int i=0;i<charArr.length;i++){
                char currentChar=charArr[i];
                //根据字符获取对应的子节点
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                   currentNode=node;
                }else{//不存在则创建一个新的叶子节点,并指向当前的叶子节点
                    node=new Trie();
                    node.value=currentChar;
                    currentNode.children[currentChar-97]=node;
                    currentNode=node;
                }
            }
            //这个标识很重要
            currentNode.endAsWord=true;
        }
    }
    /**
     * 检索指定单词是否在树中
     * @param word 单词
     */
    public boolean search(String word) {
        boolean result=true;
        if(word!=null && !word.trim().equals("")){
            char[] prefixChar=word.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                   currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
            if(result){
                result=currentNode.endAsWord;
            }
        }
        return result;
    }
    /**
     * 检索指定前缀是否在树中
     * @param word 单词
     */
    public boolean startsWith(String prefix) {
        boolean result=true;
        if(prefix!=null && !prefix.trim().equals("")){
            char[] prefixChar=prefix.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                    currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
        }
        return result;
    }
}

745. 前缀和后缀搜索 : 常规 Trie 运用题

题目描述

这是 LeetCode 上的 745. 前缀和后缀搜索 ，难度为 困难。

Tag : 「字典树」

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 WordFilter 类：

• WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
• f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 $-1$ 。

示例：

输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]

输出
[null, 0]

解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。

提示：

• $1 <= words.length <= 10^4$
• $1 <= words[i].length <= 7$
• $1 <= pref.length, suff.length <= 7$
• words[i]、pref 和 suff 仅由小写英文字母组成
• 最多对函数 f 执行 $10^4$ 次调用

基本分析

为了方便，我们令 words 为 ss，令 pref 和 suff 分别为 a 和 b。

搜索某个前缀（后缀可看做是反方向的前缀）容易想到字典树，但单词长度数据范围只有 $7$，十分具有迷惑性，使用暴力做法最坏情况下会扫描所有的 $ss[i]$，不考虑任何的剪枝操作的话，计算量也才为 $2 \times \ 7 \times 1e4 = 1.4 \times 10^5$，按道理是完全可以过的。

但不要忘记 LC 是一个具有「设定每个样例时长，同时又有总时长」这样奇怪机制的 OJ。

暴力（TLE or 双百)

于是有了 Java 总时间超时，TypeScripe 双百的结果（应该是 TypeScript 提交不多，同时设限宽松的原因）：

Java 代码：

class WordFilter {
    String[] ss;
    public WordFilter(String[] words) {
        ss = words;
    }
    public int f(String a, String b) {
        int n = a.length(), m = b.length();
        for (int k = ss.length - 1; k >= 0; k--) {
            String cur = ss[k];
            int len = cur.length();
            if (len < n || len < m) continue;
            boolean ok = true;
            for (int i = 0; i < n && ok; i++) {
                if (cur.charAt(i) != a.charAt(i)) ok = false;
            }
            for (int i = 0; i < m && ok; i++) {
                if (cur.charAt(len - 1 - i) != b.charAt(m - 1 - i)) ok = false;
            }
            if (ok) return k;
        }
        return -1;
    }
}

TypeScript 代码：

class WordFilter {
    ss: string[]
    constructor(words: string[]) {
        this.ss = words
    }
    f(a: string, b: string): number {
        const n = a.length, m = b.length
        for (let k = this.ss.length - 1; k >= 0; k--) {
            const cur = this.ss[k]
            const len = cur.length
            if (len < n || len < m) continue
            let ok = true
            for (let i = 0; i < n && ok; i++) {
                if (cur[i] != a[i]) ok = false
            }
            for (let i = m - 1; i >= 0; i--) {
                if (cur[len - 1 - i] != b[m - 1 - i]) ok = false
            }
            if (ok) return k
        }
        return -1
    }
}

• 时间复杂度：初始化操作复杂度为 $O(1)$，检索操作复杂度为 $O(\sum_{i = 0}^{n - 1} ss[i].length)$
• 空间复杂度：$O(\sum_{i = 0}^{n - 1} ss[i].length)$

Trie

使用字典树优化检索过程也是容易的，分别使用两棵 Trie 树来记录 $ss[i]$ 的前后缀，即正着存到 tr1 中，反着存到 Tr2 中。

还不了解 Trie 的同学可以先看前置 ：【设计数据结构】实现 Trie (前缀树)
前置 通过图解形式讲解了 Trie 的结构与原理，以及提供了两种实现 Trie 的方式

同时对于字典树的每个节点，我们使用数组 idxs 记录经过该节点的字符串 $ss[i]$ 所在 ss 中的下标 $i$，若某个字典树节点的索引数组 tr.idxs 为 $[a_1, a_2, ..., a_k]$ 则代表「从根节点到 tr 节点所对应的字符串」为 $ss[a_1], ss[a_2], ..., ss[a_k]$ 的前缀。

这样我们可以即可在扫描前后缀 a 和 b 时，得到对应的候选下标列表 l1 和 l2，由于我们将 $ss[i]$ 添加到两棵 tr 中是按照下标「从小到大」进行，因此我们使用「双指针」算法分别从 l1 和 l2 结尾往后找到第一个共同元素即是答案（满足条件的最大下标）。

使用 Trie 优化后，Java 从 TLE 到 AC，TypeScript 耗时为原本的 $\frac{1}{7}$ ：

Java 代码：

class WordFilter {
    class TrieNode {
        TrieNode[] tns = new TrieNode[26];
        List<Integer> idxs = new ArrayList<>();
    }
    void add(TrieNode p, String s, int idx, boolean isTurn) {
        int n = s.length();
        p.idxs.add(idx);
        for (int i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) {
            int u = s.charAt(i) - ''a'';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u];
            p.idxs.add(idx);
        }
    }
    int query(String a, String b) {
        int n = a.length(), m = b.length();
        TrieNode p = tr1;
        for (int i = 0; i < n; i++) {
            int u = a.charAt(i) - ''a'';
            if (p.tns[u] == null) return -1;
            p = p.tns[u];
        }
        List<Integer> l1 = p.idxs;
        p = tr2;
        for (int i = m - 1; i >= 0; i--) {
            int u = b.charAt(i) - ''a'';
            if (p.tns[u] == null) return -1;
            p = p.tns[u];
        }
        List<Integer> l2 = p.idxs;
        n = l1.size(); m = l2.size();
        for (int i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
            if (l1.get(i) > l2.get(j)) i--;
            else if (l1.get(i) < l2.get(j)) j--;
            else return l1.get(i);
        }
        return -1;
    }
    TrieNode tr1 = new TrieNode(), tr2 = new TrieNode();
    public WordFilter(String[] ss) {
        int n = ss.length;
        for (int i = 0; i < n; i++) {
            add(tr1, ss[i], i, false);
            add(tr2, ss[i], i, true);
        }
    }
    public int f(String a, String b) {
        return query(a, b);
    }
}

TypeScript 代码：

class TrieNode {
    tns: TrieNode[] = new Array<TrieNode>()
    idxs: number[] = new Array<number>()
}
class WordFilter {
    add(p: TrieNode, s: string, idx: number, isTurn: boolean): void {
        const n = s.length
        p.idxs.push(idx)
        for (let i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) {
            const u = s.charCodeAt(i) - ''a''.charCodeAt(0)
            if (p.tns[u] == null) p.tns[u] = new TrieNode()
            p = p.tns[u]
            p.idxs.push(idx)
        }
    }
    query(a: string, b: string): number {
        let n = a.length, m = b.length
        let p = this.tr1
        for (let i = 0; i < n; i++) {
            const u = a.charCodeAt(i) - ''a''.charCodeAt(0)
            if (p.tns[u] == null) return -1
            p = p.tns[u]
        }
        const l1 = p.idxs
        p = this.tr2
        for (let i = m - 1; i >= 0; i--) {
            const u = b.charCodeAt(i) - ''a''.charCodeAt(0)
            if (p.tns[u] == null) return -1
            p = p.tns[u]
        }
        const l2 = p.idxs
        n = l1.length; m = l2.length
        for (let i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
            if (l1[i] < l2[j]) j--
            else if (l1[i] > l2[j]) i--
            else return l1[i]
        }
        return -1
    }
    tr1: TrieNode = new TrieNode()
    tr2: TrieNode = new TrieNode()
    constructor(ss: string[]) {
        for (let i = 0; i < ss.length; i++) {
            this.add(this.tr1, ss[i], i, false)
            this.add(this.tr2, ss[i], i, true)
        }
    }
    f(a: string, b: string): number {
        return this.query(a, b)
    }
}

C++ 代码：

class WordFilter {
public:
    struct TrieNode {
        TrieNode* tns[26] {nullptr};
        vector<int> idxs;
    };
    
    void add(TrieNode* p, const string& s, int idx, bool isTurn) {
        int n = s.size();
        p->idxs.push_back(idx);
        for(int i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) {
            int u = s[i] - ''a'';
            if(p->tns[u] == nullptr) p->tns[u] = new TrieNode();
            p = p->tns[u];
            p->idxs.push_back(idx);
        }
    }
    
    int query(const string& a, const string& b) {
        int n = a.size(), m = b.size();
        auto p = tr1;
        for(int i = 0; i < n; i++) {
            int u = a[i] - ''a'';
            if(p->tns[u] == nullptr) return -1;
            p = p->tns[u];
        }
        vector<int>& l1 = p->idxs;
        p = tr2;
        for(int i = m - 1; i >= 0; i--) {
            int u = b[i] - ''a'';
            if(p->tns[u] == nullptr) return -1;
            p = p->tns[u];
        }
        vector<int>& l2 = p->idxs;
        n = l1.size(), m = l2.size();
        for(int i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
            if(l1[i] > l2[j]) i--;
            else if(l1[i] < l2[j]) j--;
            else return l1[i];
        }
        return -1;
    }
    
    TrieNode* tr1 = new TrieNode, *tr2 = new TrieNode;
    WordFilter(vector<string>& ss) {
        int n = ss.size();
        for(int i = 0; i < n; i++) {
            add(tr1, ss[i], i, false);
            add(tr2, ss[i], i, true);
        }
    }
    
    int f(string a, string b) {
        return query(a, b);
    }
};

• 时间复杂度：初始化操作复杂度为 $O(\sum_{i = 0}^{n - 1} ss[i].length)$，检索过程复杂度为 $O(a + b + n)$，其中 $a = b = 7$ 为前后缀的最大长度，$n = 1e4$ 为初始化数组长度，代表最多有 $n$ 个候选下标（注意：这里的 $n$ 只是粗略分析，实际上如果候选集长度越大的话，说明两个候选集是重合度是越高的，从后往前找的过程是越快结束的，可以通过方程算出一个双指针的理论最大比较次数 $k$，如果要将 $n$ 卡满成 $1e4$ 的话，需要将两个候选集设计成交替下标，此时 f 如果仍是 $1e4$ 次调用的话，必然会面临大量的重复查询，可通过引入 map 记录查询次数来进行优化）
• 空间复杂度：$O(\sum_{i = 0}^{n - 1} ss[i].length)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.745 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSou... 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地

本文由mdnice多平台发布

algorithm – 在ORACLE中搜索最长前缀的最快方法

select  t.gvcode,t.digits
                from NUMBERS t 
                    where 
                        t.gvcode=ZONE_SET_CODE 
                        and t.cgi=cgi_f
                       and ( PHONE_NR like t.digits)
                         order by length(digits) desc

select  t.gvcode,t.digits
from NUMBERS t 
    where 
        t.gvcode=ZONE_SET_CODE 
        and t.cgi=cgi_f
       and PHONE_NR like t.digits
       and substr(digits,length(digits)-1) <= PHONE_NR
       and rpad(substr(digits,'9') >= PHONE_NR
order by length(digits) desc

关于在基数树/ patricia trie中搜索前缀和写出下列基数词的序数词的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于014 - 数据结构 - 树形结构 - 基数树、Patricia 树、默克尔树、梅克尔帕特里夏树 (Merkle Patricia Tree, MPT)、208-实现 Trie (前缀树)、745. 前缀和后缀搜索 : 常规 Trie 运用题、algorithm – 在ORACLE中搜索最长前缀的最快方法等相关知识的信息别忘了在本站进行查找喔。