【6】字典树学习笔记

前言

WFLS 2023 寒假集训 Day2

大纲里字典树在数据结构里，但是个人认为应该属于字符串，就把它放到字符串里了

字典树

字典树，又称Trie树，字母树。每个顶点代表一个字符，从根节点到叶子节点的路径上所有的节点的字符连接起来，就是一个字符串。

字典树的优点：利用串的公共前缀来节省内存，加快检索速度。

注意：字典树根节点为空

同时，字典树也是很多字符串算法的基础——比如AC自动机。

节点定义

使用数组模拟指针

int trie[100010][26],sum[100010],cnt=0;

插入操作

从根节点开始，如果字符节点未存储，就开辟一个新节点；否则就直接使用已有的字符前缀。然后访问下一个节点，重复执行此操作，直到字符串末尾。最后将计数器自增，表示添加一个字符串。

void insert(char str[])
{int root=0,i=0;int l=strlen(str);for(i=0;i<l;i++){int id=str[i]-'a';if(!trie[root][id])trie[root][id]=++cnt;root=trie[root][id];}sum[root]++;
}

查询操作

从根节点开始，如果字符节点未存储，证明为存储这个字符串，返回 $0$ 。否则一直访问到字符串末尾，返回字符串的计数。

int search(char str[])
{int root=0,i=0;int l=strlen(str);for(i=0;i<l;i++){int id=str[i]-'a';if(trie[root][id])root=trie[root][id];else return 0;}return sum[root];
}

复杂度分析

时间复杂度： $O(length)$ （和 $O(n)$ 与 $O(\log n)$ 不是同一层级的概念）

空间复杂度：略

字典树例题

例题 $1$ ：

字符串统计（trie树模板）（站外题，提供体面展示）

---

题目描述

维护一个字符串集合，支持两种操作：

$1$ . I x 向集合中插入一个字符串 $x$ ；

$2$ . Q x 询问一个字符串在集合中出现了多少次。

共有N个操作，输入的字符串总长度不超过 $10^5$ ，字符串仅包含小写英文字母。

输入格式

第一行包含整数 $N$ ，表示操作数。

接下来 $N$ 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x ，都要输出一个整数作为结果，表示 $x$ 在集合中出现的次数。

每个结果占一行。

输入样例

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例

1
0
1

数据范围

$1\le N\le 2\times 10^4$

---

字典树板子题，不多赘述。

#include <bits/stdc++.h>
using namespace std;
int n=0,trie[100010][26],sum[100010],cnt=0,root=0;
char ch,str[100010];
void insert(char str[])
{int root=0,i=0;int l=strlen(str);for(i=0;i<l;i++){int id=str[i]-'a';if(!trie[root][id])trie[root][id]=++cnt;root=trie[root][id];}sum[root]++;
}int search(char str[])
{int root=0,i=0;int l=strlen(str);for(i=0;i<l;i++){int id=str[i]-'a';if(trie[root][id])root=trie[root][id];else return 0;}return sum[root];
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){getchar();getchar();scanf("%c%s",&ch,str);if(ch=='I')insert(str);else if(ch=='Q')printf("%d\n",search(str));}return 0;
}

例题 $2$ ：

UVA11362 Phone List

双倍经验

UVA644 Immediate Decodability

字典树除了用来查单词，还可以用来查前缀。

用 $ap[i]=1$ 表示编号为 $i$ 的节点为某个字符串的结尾。

在插入字符串时，会遇到两种情况：

$1$ ：插入一个字符串，没有建立任何新的节点。证明这个字符串已经被另一个字符串包含，是某个字符串的前缀。

$2$ ：插入一个字符串，经过了某个 $ap[i]=1$ 的节点。证明这个字符串包含了另一个字符串，某个字符串是这个字符串的前缀。

综合这两条性质判定即可，注意是数字串。

UVA11362

#include <bits/stdc++.h>
using namespace std;
int t,n=0,trie[100010][10],ap[100010],cnt=0;
char ch,str[100];
bool insert(char str[])
{int root=0,i=0,flag1=0,flag2=1;int l=strlen(str);for(i=0;i<l;i++){int id=str[i]-'0';if(!trie[root][id])flag2=0,trie[root][id]=++cnt;root=trie[root][id];if(ap[root])flag1=1;}ap[root]=1;return flag1||flag2;
}int main()
{scanf("%d",&t);for(int i=0;i<t;i++){bool flag=0;scanf("%d",&n);for(int i=0;i<=cnt;i++){ap[i]=0;for(int j=0;j<10;j++)trie[i][j]=0;}cnt=0;for(int j=0;j<n;j++){scanf("%s",str);flag=flag||insert(str);}if(flag)printf("NO\n");else printf("YES\n");}return 0;
}

UVA644

#include <bits/stdc++.h>
using namespace std;
int t,n=0,trie[100010][10],ap[100010],cnt=0;
char ch,str[100];
bool insert(char str[])
{int root=0,i=0,flag1=0,flag2=1;int l=strlen(str);for(i=0;i<l;i++){int id=str[i]-'0';if(!trie[root][id])flag2=0,trie[root][id]=++cnt;root=trie[root][id];if(ap[root])flag1=1;}ap[root]=1;return flag1||flag2;
}int main()
{int z=0;while(1){bool flag=0;z++;for(int i=0;i<=cnt;i++){ap[i]=0;for(int j=0;j<10;j++)trie[i][j]=0;}cnt=0;while(1){if(scanf("%s",str)==EOF)return 0;if(str[0]!='9')flag=flag||insert(str);else break;}if(flag)printf("Set %d is not immediately decodable\n",z);else printf("Set %d is immediately decodable\n",z);}return 0;
}

例题 $3$ ：

P2922 [USACO08DEC]Secret Message G

同样是求前缀的题目，但这次增加了对数量的查询，并且换为了01串。

用 $ap[i]=1$ 表示编号为 $i$ 的节点为某个字符串的结尾。

$1$ ：插入一个字符串，没有建立任何新的节点。证明这个字符串已经被另一个字符串包含，是某个字符串的前缀。这时可以加上对前缀的计数，也就是在插入的过程中经过的每一个节点计数器都自增。

$2$ ：插入一个字符串，经过了某个 $ap[i]=1$ 的节点。证明这个字符串包含了另一个字符串，某个字符串是这个字符串的前缀。可以知道，被经过的 $ap[i]=1$ 的节点都是此串的前缀，直接加到答案里就行。

注意特判两种情况编号相同的节点，这类节点只应该算一次。

另外，由题目中：

这个前缀长度必须等于暗号和那条信息长度的较小者

中途失配时 $ans$ 不能加，否则你会收获 $7$ 分的好成绩。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010],trie[5200010][3],ap[5200010],sum[5200010],cnt=0,ans=0;
void insert(int a[],int l)
{int root=0,i=0;for(i=0;i<l;i++){int id=a[i];if(!trie[root][id])trie[root][id]=++cnt;root=trie[root][id];sum[root]++;}ap[root]++;
}int search(int a[],int l)
{int root=0,i=0,ans=0,ros=0,flag=1;for(i=0;i<l;i++){int id=a[i];if(trie[root][id])root=trie[root][id];else {flag=0;break;}}if(flag)ros=root,ans+=sum[ros];root=0;i=0;for(i=0;i<l;i++){int id=a[i];if(trie[root][id])root=trie[root][id];else break;if(root!=ros)ans+=ap[root];}return ans;
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++){int l;scanf("%d",&l);for(int j=0;j<l;j++)scanf("%d",&a[j]);insert(a,l);}for(int i=0;i<m;i++){int l;scanf("%d",&l);for(int j=0;j<l;j++)scanf("%d",&a[j]);printf("%d\n",search(a,l));}return 0;
}

例题 $4$ ：

【一本通提高篇Trie字典树】The XOR Largest Pair（站外题，提供题面展示）

---

题目描述

给定的 $n$ 个整数 $A_1,A_2,A_3\dots A_n$ 中选出两个进行异或运算，最后最大结果是多少

输入格式

第一行一个整数 $n$

第二行 $n$ 个整数 $A_i$

输出格式

一个最大结果

样例输入

5
2 9 5 7 0

样例输出

14

提示

$n\le 10^5,0\le A_i<2^{31}$

---

第一次看到这题，绝对不会想到字典树。

首先 $n\le 10^5$ ，$O(n^2)$ 暴力别想，然后由于异或是位运算，开始考虑二进制拆分。

可以把二进制拆分拆出来的数字存到一棵字典树里，然后枚举 $A_i$ 参与异或运算。

为了最大化异或结果，从高位开始，每次在字典树上选择的二进制位最好与 $A_i$ 的二进制位相异，否则这一位只能是 $0$ 。这样可以让高位出现更多的 $1$ ，从而最大化异或结果。

注意，这里的二进制拆分可以当场位运算算出来，并不需要事先拆好。

int id=(a>>i)&1;

同样，对结果的计算也是可以遍查询边位运算算的。

ans=(ans<<1)+1;
ans=(ans<<1);

其实很多异或的题目都是可以这样做的。

#include <bits/stdc++.h>
using namespace std;
int n,a[100010],trie[3200010][10],cnt=0,ans=0;
void insert(int a)
{int root=0,i=0;for(i=31;i>=0;i--){int id=(a>>i)&1;if(!trie[root][id])trie[root][id]=++cnt;root=trie[root][id];}
}int search(int a)
{int root=0,i=0,ans=0;for(i=31;i>=0;i--){int id=(a>>i)&1;if(trie[root][!id])root=trie[root][!id],ans=(ans<<1)+1;else root=trie[root][id],ans=(ans<<1);}return ans;
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);insert(a[i]);}for(int i=0;i<n;i++)ans=max(ans,search(a[i]));printf("%d",ans);return 0;
}

后记

字典树明明比KMP简单，竟然评 $6$ 级。

真没想到，我学的第一棵树竟然是字典树。

以后如果还有再做的题，会补进来的。