【本文概要】本文主要介绍了字典树的概念，字典树的一般算法，包括初始化，插入，查找等，最后举了比较典型的案例以及算法比赛中常见的“01树”来辅助理解字典树这种特殊的数据结构。

1、什么是字典树

        字典树，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。一般而言，我们认为字典树是一种前缀树，但有时它也可以是后缀树（具体见下图）。字典树在统计、保存大量字符串中有着极大的优势：它利用字符串的公共前缀或后缀来减少查询时间，最大限度地减少不必要的字符串比较，使得查询的效率比一般算法高得多。

        如上图所示，常见的字典树的每一个节点是由一个数据域（用来标记是否在此处有字符串终止）与一个长度为26的指针域（表示26个小写字母）组成。一般我们在根结点不存储任何数据，这样是为了可以存储所有的字符串，从根结点到某一个节点，路过的字符连起来就是该节点对应的字符串。由于每个节点的子节点字符不同，也就是说明找到对应单词、字符是唯一的。

2、字典树的实现

        这里我们整理字典树的定义、插入和查找的相应算法的写法。

2.1 字典树的定义

const int size = 26;
struct Node {bool k; // true表示有字符串在此结尾，false表示无字符串在此结尾Node* next[size];Node() :k(false) { // 给成员变量赋值falsefor (int i = 0; i < size; ++i) {next[i] = nullptr; // 初始化都是空指针}}
};

2.2 字典树的插入

void insert_ch(char *ch) {Node *p = head;for (int i = 0; ch[i]; ++i) {if (p->next[ch[i] - 'a'] == nullptr) // 判断下层节点是否存在p->next[ch[i] - 'a'] = new Node; // 开辟新空间p = p->next[ch[i] - 'a'];}p->k = true; // 进行字符串结尾标记
}

        每次从根节点进行插入，如果向下的节点已经存在，就直接读取，否则拓展一个新节点。之后将最后一个节点的k标记为true表示该位置有一个字符串结尾。

2.3 字典树的查找

bool find_ch(char *ch) {Node *p = head;for (int i = 0; ch[i]; ++i) {if (p->next[ch[i] - 'a'] == nullptr) { // 判断下层节点是否存在return false; // 不存在即判否}p = p->next[ch[i] - 'a'];}return p->k; // 最终判断
}

        基本过程与插入相同，向下查找，入过该节点不存在，直接返回false，如果存在一直向下查找，最终返回末尾标记的k。

3、关于字典树的常见问题整理

3.1 依依的瓶中信

//本题考察字典树的扩展应用
//其具体算法仍是字典树的插入与查询
//需要注意的是当前字符串不能与自己匹配,
//解决的方法是写一个删除函数,先将当前字符串删除再查询,查询后再恢复 
//由于插入与删除的本质相同,只是cnt数组对应位置的增加或减小,故只需改写插入函数即可 
#include <bits/stdc++.h>using namespace std;const int maxn=1e5+100;string str[maxn];//存储原始字符串组 
int nex[maxn][27];//nex[x][0]表示从第x个结点出发,边为'a'的下一个结点地址 
int cnt[maxn];//cnt[i]表示以第i个结点结尾的前缀的数量 
int idx=2;//用于动态开点 void Insert(string s,int tag)//将字符串s插入字典树中,或将其从字典树中删除
//若传入tag=1,则为插入;若传入tag=-1,则为删除
//插入与删除的本质是令对应的cnt[x]+1或-1 
{int x=1;//初始从根结点(1号)开始 for(int i=0;i<s.size();i++)//遍历字符串s {cnt[x]+=tag;//对每个字符,以该字符结尾的前缀数量均+1/-1 if(nex[x][s[i]-'a']==0)//若该字符(存储该字符的边)未被记录 {nex[x][s[i]-'a']=idx++;//则动态开点并记录之 }x=nex[x][s[i]-'a'];//继续向下追溯 }        cnt[x]+=tag;//结尾字符对应的前缀数量+1/-1 
}int Search(string s)//在字典树中查找与s最接近的字符串,并返回匹配的最长前缀的长度 
{int x=1;//初始从根结点(1号)开始 int ans=0;//记录匹配的最长前缀的长度 for(int i=0;i<s.size();i++)//遍历字符串 {if(nex[x][s[i]-'a']==0)//已经无法再匹配(不存在记录当前字符的边){return ans;//返回之前累计的长度 }    x=nex[x][s[i]-'a'];//若能继续匹配,则继续向下追溯 if(cnt[x]==0)return ans;//已经不存在以x结点结尾的前缀,返回之前累计的长度//注意以上这句不可省略,因为在删除操作中只是减少了字符串出现的次数,并没有删除之前记录的字符 ans++;//计数值加1,重复上述操作 }    return ans;//最终返回ans 
}int main()
{int N;cin>>N;for(int i=0;i<N;i++)//输入N个字符串 {cin>>str[i];Insert(str[i],1);//插入 }for(int i=0;i<N;i++)//N组查询 {Insert(str[i],-1);//先将当前字符串删除 cout<<Search(str[i])<<endl;//查询匹配的最长前缀的长度并输出 Insert(str[i],1);//将当前字符串重新插入以恢复字典树 }return 0;
}

3.2 XOR的最大值

这道题使用了字典树的特例——01树，这里简单做个介绍：

// 本题考察的是字典树的一个特例——01树
// 01树的一个常见用处就是用来查找异或最大值
// 由于查找过程类似二分，大大减少了所用的时间
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int son[32 * N][2], tot = 1; // 表示每个节点的子节点，节点编号// 在01树中插入新的数
void insert(int num) {int o = 1; // 从第一层开始插入，深度较小的节点存储数的高位for (int i = 30; i >= 0; --i) { // 这里的最高层数是一个估计值，大约30位int bit = num >> i & 1; // num的第i位if (!son[o][bit]) { // 如果这个子节点之前未被创建son[o][bit] = ++tot; // 那么就给这个新的子节点编上序号} // 这里节点覆盖不影响之后的查找，因为查找过程中只需要确定这个数存在即可，// 并不关注这个数的编号o = son[o][bit]; // 之后就从这个子节点所在序号处继续插入}
}// 在01树中查找异或最大值
int query(int num) {int o = 1, res = 0;for (int i = 30; i >= 0; --i) {int bit = num >> i & 1;if (son[o][!bit]) { // 如果该位的不同数节点存在o = son[o][!bit]; res |= 1ll << i; // 那么就证明存在一个数的该位可以通过异或产生有效位} // 这里利用了二进制的一个特殊之处在于第i位为1形成的数大于从第0位到第i-1位均为1形成的数else {o = son[o][bit];}}return res;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin >> n;for (int i = 1; i <= n; ++i) {int x; cin >> x;insert(x);}int q; cin >> q;while (q--) {int x; cin >> x;cout << query(x) << "\n";}
}