【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树模板）（站外题，提供体面展示）

题目描述

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

$2$ . `Q x` 询问一个字符串在集合中出现了多少次。 共有N个操作，输入的字符串总长度不超过 $10^5$ ，字符串仅包含小写英文字母。 ### 输入格式 第一行包含整数 $N$ ，表示操作数。 接下来 $N$ 行，每行包含一个操作指令，指令为 `I x` 或 `Q x` 中的一种。 ### 输出格式 对于每个询问指令 `Q x` ，都要输出一个整数作为结果，表示 $x$ 在集合中出现的次数。 每个结果占一行。 ### 输入样例 ```latex 5 I abc Q abc Q ab I ab Q ab ``` ### 输出样例 ```latex 1 0 1 ``` ### 数据范围 $1\le N\le 2\times10^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 的节点为某个字符串的结尾。

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

$2$ ：插入一个字符串，经过了某个 $ap[i]=1$ 的节点。证明这个字符串包含了另一个字符串，某个字符串是这个字符串的前缀。 综合这两条性质判定即可，注意是数字串。 UVA11362 ```cpp #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 ```cpp #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](https://www.luogu.com.cn/problem/P2922) 同样是求前缀的题目，但这次增加了对数量的查询，并且换为了01串。 用 $ap[i]=1$ 表示编号为 $i$ 的节点为某个字符串的结尾。 $1$ ：插入一个字符串，没有建立任何新的节点。证明这个字符串已经被另一个字符串包含，是某个字符串的前缀。这时可以加上对前缀的计数，也就是在插入的过程中经过的每一个节点计数器都自增。 $2$ ：插入一个字符串，经过了某个 $ap[i]=1$ 的节点。证明这个字符串包含了另一个字符串，某个字符串是这个字符串的前缀。可以知道，被经过的 $ap[i]=1$ 的节点都是此串的前缀，直接加到答案里就行。 注意特判两种情况编号相同的节点，这类节点只应该算一次。 另外，由题目中： >这个前缀长度必须等于暗号和那条信息长度的较小者 中途失配时 $ans$ 不能加，否则你会收获 $7$ 分的好成绩。 ```cpp #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](http://www.accoders.com/problem.php?id=2082)（站外题，提供题面展示） *** ### 题目描述 给定的 $n$ 个整数 $A_1,A_2,A_3\dots A_n$ 中选出两个进行异或运算，最后最大结果是多少 ### 输入格式 第一行一个整数 $n

第二行 n 个整数 A_i

输出格式

一个最大结果

样例输入

5
2 9 5 7 0

样例输出

14

提示

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

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

首先 n\le10^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 级。

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

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