当前位置：首页 > article >正文

【6】字典树学习笔记

article 2025/3/12 11:47:20

前言

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 (l e n g t h)$ （和 $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\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

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

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

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

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

$2$ ：插入一个字符串，经过了某个 $a p [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串。

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

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

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

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

另外，由题目中：

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

中途失配时 $an s$ 不能加，否则你会收获 $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

样例输出

提示

$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;
}