书接去年今天作业不想写了滚过来写总结。顺便保留我刚略微学会的串串。声明作者由于水平不高所以有些定理不能严谨证明所以若是初学者请移步别处。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(cAcZ) return c-A; else if(cacz) return c-a26; else return c-052; } void add(string s){ lens.size(); s s; int p0; for(int i1;ilen;i){ int idgetid(s[i]); if(!tr[p][id]) tr[p][id]idx; ptr[p][id]; cnt[p]; } } ll ask(string s){ lens.size(); s s; int p0; for(int i1;ilen;i){ int idgetid(s[i]); if(!tr[p][id]) return 0; ptr[p][id]; } return cnt[p]; }空间这块最坏情况每个字符串的每个字符都要新开一个节点所以空间开即可。上一道例题AT_arc219_a [ARC219A] SimilarityAT_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树上找不到后缀时就直接无脑连根结点