非线性字符串数据结构串讲

书接去年，今天作业不想写了，滚过来写总结。顺便保留我刚略微学会的串串。

声明：作者由于水平不高，所以有些定理不能严谨证明，所以若是初学者请移步别处。

1.Trie树

定义

Trie树又叫字典树，是非常显然的一种字符串数据结构。

具体来说，我们如果手上有很多字符串，我们可以通过建一个Trie树来做一些简单的操作。

其构建过程可以看一下图，非常显然，本质就是把字符串的相同部分压缩一下。

比如我们对

aa aba ba caaa cab cba cc

建一个Trie就长这样。

构建

图来自OI wiki

然后构建这块也挺简单的

代码

int len,idx,cnt[N],tr[N][70]; ll getid(char c){ if(c>='A'&&c<='Z') return c-'A'; else if(c>='a'&&c<='z') return c-'a'+26; else return c-'0'+52; } void add(string s){ len=s.size(); s=' '+s; int p=0; for(int i=1;i<=len;i++){ int id=getid(s[i]); if(!tr[p][id]) tr[p][id]=++idx; p=tr[p][id]; cnt[p]++; } } ll ask(string s){ len=s.size(); s=' '+s; int p=0; for(int i=1;i<=len;i++){ int id=getid(s[i]); if(!tr[p][id]) return 0; p=tr[p][id]; } return cnt[p]; }

空间这块，最坏情况每个字符串的每个字符都要新开一个节点，所以空间开即可。

上一道例题

AT_arc219_a [ARC219A] Similarity

AT_arc219_a [ARC219A] Similarity

正难则反

这个比较困难

所以就把S串01翻转，那么就是找出一个串串使得不能与任何一个S串相同。

那你给这些反串建出Trie后，找一个还没有被经过的节点即可。

例题结束

与异或相关

其实我们的Trie树不只能在字符串上用

因为在我们眼里数是有二进制的，二进制我们就可以想到01串。

我们就可以把数字当做01串建Trie树

当我们遇到一些神秘有关异或的题目时，

我们一想Trie树，二想线性基

比如来道题，给定你一个序列和x值，让你从这个序列中选一个元素，使之其与x的异或值最大。

考虑异或的性质，二进制位上不同为一，相同为0。

所以我们对序列建Trie树，把给定的x二进制分解，从高往低位的贪心的尽可能与x当前位不同。就行了。

来一道有意思的应用

P5283 [十二省联考 2019] 异或粽子

题解

2.AC自动机

AC自动机，由两部分构成Trie树和fail树。

AC自动机的本质上就是建出Trie树后连fail边。

这里我们给出fail边的定义。

在Trie树上,每一个节点表示一个字符串。

fail边指向这个节点所代表的字符串 最长的后缀 所代表的节点。

example：

图来自OI wiki

比如这个Trie树

给他建fail边就应该是这样的

由于根节点代表的是空串，空串是任何字符串的后缀。

所以当你实在在Trie树上找不到后缀时，就直接无脑连根结点