后缀树

后缀树是相较于$AC$自动机的另一种用于多模字符串匹配算法，虽然两者都基于字典树$Trie$,但是一种是对主串预处理，一种是对模式串预处理。 后缀树的$Trie$并不是标准的后缀树，而是压缩$Trie$。意思是若一个节点到另一个节点的路径上的节点都没有出边，那么将其压缩为一条边，可以节省空间。 后缀树可以用$O(n^2)$暴力构建，具体流程如下： >1.新建一棵字典树。 >2.将主串的所有后缀依次插入后缀树。 >3.将该后缀树压缩成压缩$Trie$。