字典树（Trie）¶

简介¶

字典树（Trie）是一种用于存储字符串的树形数据结构。它可以有效地进行字符串的查找和插入操作，特别适合处理大量字符串的场景，支持多种操作：

插入：插入一个新的字符串到字典树当中。
查询：查询当前字典树内是否存在指定的字符串。

AC自动机可以视为在字典树上的KMP算法，所以字典树是AC自动机的一个前置知识。

在这里放一张图（From OI-Wiki）：

trie1

可以发现，在字典树当中，每一条边都代表了一个字母，从根节点到叶子节点的一条路径就构成了一个字符串。

但是这张图中没有展示一个字符串是已有字符串的前缀的情况，在这种情况下，会出现一个字符串结束了，但是其结束节点并不是叶子结点，例如car和cartoon。我们可以通过在每个节点维护一个布尔类型的表示，记录是否有 以当前节点为结尾的字符串存在 来解决。

复杂度分析¶

字典树插入和查询操作的时间复杂度均为 \(O(L)\)，其中 \(L\) 为字符串的长度。这个复杂度与字典树中已有的字符串数量无关，只与操作字符串的长度有关。

字典树的空间复杂度为 \(O(Size \times N \times M)\)，其中 \(N\) 为字符串的数量，\(M\) 为字符串的平均长度，\(Size\)为字符空间大小（小写字母集的\(Size=26\)）。在实际比赛中，由于不同字符串会共享前缀，实际空间使用通常会小于这个上界。

变种¶

01字典树¶

01字典树是字典树的一种特殊形式，专门用于处理二进制数字。它将每个数字看作一个01字符串，从最高位开始逐位插入到字典树中。01字典树常用于解决以下问题：

最大异或值：给定一个数组，求出数组中任意两个数异或的最大值。可以通过在01字典树中查找与当前数字尽可能不同的路径来实现。
第k大异或值：结合字典树的节点计数，可以查找所有数字与某个数字异或后的第k大值。

可持久化字典树¶

可持久化字典树是字典树的可持久化版本，它支持查询历史版本的信息。可持久化字典树常用于解决以下问题：

区间异或第k大：给定一个数组，多次查询某个区间内与指定数字异或后的第k大值。
字符串历史版本查询：在某些需要维护字符串历史版本的场景中，可持久化字典树可以提供高效的查询。

实现¶

初始化¶

在本文中，我们使用结构体数组进行字典树的存储，具体来说：

const int MAXN = 1e5;

struct Node{
    int next[26];
    bool exist = false;
}trie[MAXN];

在这个结构体当中，我们采用一个int next[]数组存储节点间关系。next[]数组的大小由题目中的字符集大小决定（若字符集为所有小写英文字母，则字符集大小为26）；使用一个 bool exist 来存储是否有以该节点为结尾的字符串；

在实际使用中，我们还需要在插入和查询前将字典树初始化：

void init(){
    for(int i=0; i<=eCnt; i++){
        memset(trie[i].next, 0, sizeof(trie[i].next));
        trie[i].exist = false;
    }
    eCnt = 0;
}

这段代码将所有节点的next[]数组清零，并将exist属性设为false，然后将节点计数器eCnt重置为0。

插入¶

int eCnt = 0;

void insert(string a){
    int idx = 0;
    for (auto ch : a){
        if (! trie[idx].next[ch-'a']) trie[idx].next[ch-'a'] = ++eCnt;
        idx = trie[idx].next[ch-'a'];
    }
    trie[idx].exist = true;
}

我们维护一个变量 int eCnt 用于分配新的节点编号，从 \(1\) 开始，\(trie[0]\) 为根节点。

通过遍历传入的字符串，查找是否存在与当前字符串相符的边，如果不存在，则创建一个新的节点并连一条与之相符的边。

最后将结尾节点的 exist 属性设为 true 表示 有以该节点为结尾的字符串。

查询¶

bool query(string a){
    int idx = 0;
    for (auto ch : a){
        if (! trie[idx].next[ch-'a']) return false;
        idx = trie[idx].next[ch-'a'];
    }
    return trie[idx].exist;
}

查询操作与插入操作类似，也是从根节点开始遍历字符串。如果在遍历过程中发现某个字符对应的边不存在，则说明该字符串不在字典树中，直接返回 false。如果遍历完整个字符串，检查最后一个节点的 exist 属性，如果为 true 则说明该字符串存在于字典树中。