前言

$Trie$真的是一个数据结垢中的清流(个人感受)

刷了几道题已经体验到它的恶心了,但是板子比树状数组都还容易理解,fa不多说,一起来看看这个数据结垢吧!


正文

ud:首先要明确的是,它是一种用树的形式存储,利用相同前缀不反复搜索的特性的一个数据结构。是空间换时间的一个典型例子。

首先要明确的是,它所能够解决的,是一种什么类型的问题。

先来看这样一个问题:

现在要求维护一个字符串集合,要求可以完成以下两种操作:

1.I str:向集合里插入一个字符串str

2.Q str:查询字符串str在集合中出现的次数。

题面链接

这道题当然可以用STLmap水过,但是我们是来学习Trie的

1.存储(insert)

$Trie$别名前缀树,所以我们来看看它是怎么通过前缀来记录字符串的。

首先要明确,每个节点存储了一个字符。比如插入abc之后的前缀树长这样:

Trie1.jpg

(图很简陋)但是思想就是这样的。也许这样看不太明显,我们换一个。假设我们不仅插入了abc,还插入了abd,acd,bcd,来看一下效果:

Trie2.jpg

所以,相同的前缀不会反复存储(虽然也很耗空间就是了)

然而只进行存储是不够的,我们还要查询每个串在集合出现的次数呢。怎么理解这个次数呢?

我们对每个插入的串的末尾进行统计,即每次记录这个串到末尾,就把这个末尾对应的计数加一。

因为还有记录编号,所以我们要重新考虑存储。考虑用c[r][v]记录父节点编号为r,自身字符记录为v的结点编号。这个v,我们可以用字符的ASCll码来进行操作。于是我们定义一个全局变量idx记录编号。

变量名意义:
idx:编号计数
c[r][v]:父节点编号为r,自身元素表示为v的点的编号
cnt[r]:编号为r的点的 附加信息 。(根据题目而定)

代码块如下:

void isrt(char str[])
{
    int r=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';//把字符转换成数字
        if(!c[r][u])c[r][u]=++idx;//如果没有出现过,分配编号
        r=c[r][u];//不断向下
    }
    cnt[r]++;
}

所以对于顺次插入abc,abd,acd,bcd的操作,我们可以进行一下模拟:(c数组的第二维的数字由对应字母的ASCll码减去'a',以下不再解释)

1.插入"abc"
r=0;
1.1.插入'a':c[0][0]还没有值,c[0][0]=1,r=1;
1.2.插入'b':c[1][3]还没有值,c[1][3]=2,r=2;
1.3.插入'c':c[2][5]还没有值,c[2][5]=3,r=3;
2.插入"abd"
r=0;
2.1.插入'a':c[0][0]有值了,r=c[0][0]=1;
2.2.插入'b':c[1][7]有值了,r=c[1][8]=2;
2.3.插入'd':c[2][3]还没有值,c[2][3]=4,r=4;
3.插入"acd"
r=0;
3.1.插入'a':c[0][0]有值了,r=c[0][0]=1;
3.2.插入'c':c[1][9]还没有值,c[1][9]=5,r=5;
3.3.插入'd':c[5][3]还没有值,c[5][3]=6,r=6;
4.插入"bcd"
r=0;
4.1.插入'b':c[0][1]还没有值,c[0][1]=7,r=7;
4.2.插入'c':c[7][2]还没有值,c[7][2]=8,r=8;
4.3.插入'd':c[8][3]还没有值,c[8][3]=9,r=9;

所以和上面的图一样,一共有9个结点,我们给他们标上号:

查询(ask/query)

那么怎么样查询一个前缀出现的次数呢?回到我们的代码块部分,发现最后还有一句cnt[r]++,是什么意思呢?

这么做了之后,cnt数组就有了一个特别的意义,即以这个点结尾的前缀的个数

比如在这个图中,cnt[3]=1,cnt[4]=1,cnt[6]=1,cnt[9]=1

这么记录之后有什么好处呢?比如我要查询一个串"abc"在串里出现的次数,我只需要从根节点开始往下,只要还有能够和我匹配的路径,就一直往下层走。比如这次查询的路线就是"root->1->2->3",因为路径中没有不匹配的字符,所以最终的答案就是cnt[3]

为什么这样做是正确的?因为要到这个串被标记的结束位置,一定会走和这个串相同的路径。而我们为了保证它们是完全匹配的,所以只需要知道查询串匹配完成之后的点的标记值,输出就可以了。

如果遇到不匹配的,比如"abe","abcd","ab",我们都分别来尝试看一下它们查询所走的路径。

对于"abe",匹配过程为"root->1->2->return 0";

对于"abcd",匹配过程为"root->1->2->3->return 0";

对于"ab",匹配过程为"root->1->2 return cnt[2] (虽然也是0)"

所以,实现的代码和思路都是比较容易理解的,下面放上代码块:

int ask(char str[])
{
    int r=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';//往下匹配的关键字
        if(!tr[r][u])return 0;//如果失配,直接返回
        r=tr[r][u];//继续往下
    }
    return cnt[r];//匹配全部完成,返回以这个点结尾的前缀的数的个数
}

最后,完整代码奉上。


例题部分

相信大家都已经理解了(强行)

其实Trie的思想就那么简单。只是需要灵活的变通,就比较困难。接下来放几个例题让大家感受一下,就不详细的讲解了。

ps.难度由个人感受从易到难


查单词

题目大意:每个字符串对应一个整数(页码),给出所有有对应关系的字符串及其页码之后,查询其中某些单词的页码。($O(n^2)-TLE$)

思路:依然正常插入字符串,但是在结尾标记处把加一改成赋值为页码,查询到了直接返回对应页码,而且因为查询串一定出现过,所以甚至不用判断就可以直接跑,是一道氵题。

参考代码


统计难题

题目大意:给出一些文本串和一些询问串,要求输出以每个询问串为前缀的文本串的个数。

思路:这里打标记的思路就要更改一下。因为要求询问串是文本串的前缀,也就是询问串完全覆盖文本串,所以我们只需要把文本串一路上经过的所有结点的cnt加一,输出询问串末端的结点的cnt值即可。

参考代码


最大异或对

题目大意:给出$n(n≤1e5)$个整数,求其中异或值最大的一对的异或值(好像有点绕)。

思路:这道题就比较有意思,要抽象成Trie就有一点困难。稍微说详细一点。

首先是暴力做法,肯定是外层循环1->n,内层循环1->n,找到一个最大的a[i]^a[j]。但是弊端很明显,需要花费的时间太多了。

那我们怎么优化呢?先要看清内层循环的实质。内层循环实际就是给外层循环找到一个最大的值,使它们异或起来值最大。再根据异或运算的法则,我们可以发现,从二进制串的最高位往下,要尽可能使得两个数的同一个位置的数不同,这样才能让异或值最大。理解清楚了这一点之后,就比较容易考虑到如何解题了。

具体就是,先把所有数字的二进制串从高位到低位(31->1)插入到Trie中,末尾标记为这个数字,因为每个数字对应的二进制串长度相同,所以不会出现重复记录的情况。然后对于每一个a[i],找到一个合适的a[j],从高向低,尽可能走与a[i]不同的路线,即如果可以走与当前这一位的a[i]的值不同的路线,就这样走,否则才和a[i]走相同的路线。最后把所有结果统计取Max就可以了。

参考代码


Chip Factory

题目大意:最大异或对plus!依然给出一个长度为n的序列s,要求从s中选取三个各不相同的数字i,j,k,使得(s[i]+s[j]) xor s[k]的值最大。

思路:核心思路依然是最大异或对。每次拿s[i]+s[j]去匹配最大的异或值。但是题目要求三个数各不相同,所以我们的k不能选中i或者是j。这个操作就需要我们的删除操作登场了!

在上一道题,我们在二进制串的末尾计数加一,现在依然保留,把它记做cnt2[],除此之外,我们还要用到第二题的操作:经过的结点都计数加一,记做cnt1[]。明显,cnt2[]是用来完成匹配操作的(同上题),我们利用cnt1[]来进行删除操作也是很简单的。

要删除一个数,只需要把它再“插入”一次,但是正常的插入操作中是cnt1[r]++,在删除操作,我们改成cnt1[r]--。为什么这样做呢?假如有一条路径只有这个串经过,本身的计数值是1,我们减去之后就是0了,不应该继续经过,所以只需要在匹配的时候判断要走的点是否还满足可以走,即cnt[r]!=0的条件就可以了。

参考代码


Phone List

题目大意:给出一些字符串,问每组字符串里是否有某个串是另一个的子串。即:有没有某个字符串覆盖了另一个字符串。有就输出"NO",没有就输出"YES"。

思路:要求是否有被覆盖的串,我们首先得保证被覆盖的串较短。而要让可能被覆盖的串全都被判断到的话,还需要保证插入的字符串长度递增即可。所以我们先以串的长度作为关键字进行从小到大的排序,再挨着插入,插入的时候在串的末尾进行标记。如果在插入过程中遇到了被标记过的结点,说明这组数据中有被覆盖的串,想办法输出就好了233

参考代码


越写越多啊咧...暂时就先这样吧,以后如果遇到有趣的Trie的题也会更新过来(亿万年以后也不可能)

最后修改:2020 年 08 月 17 日 11 : 45 PM