字典树 (Trie)
Trie¶
先考虑怎么存多个串
一种树，每个结点有 个儿子，每条边表示一个字符
空间 （如果假设 为常数）
要判断某个串是否等于某个模式串，只要在 Trie 上走一遍（线性的）
在 Trie 上 KMP¶
实际上要做的事情是求出 Trie 的每个节点的 值
当然，这里的 不再是一个值，而是相当于是一个指针——它可能指向其他分支的节点。
这时 的定义：最长的等于同长度的后缀的从根开始的路径的长度
复杂度：均摊分析失效了，其实只能在每条链上均摊分析，于是总复杂度为模式串长总和
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用