跳转至

字典树 (Trie)

Trie

先考虑怎么存多个串

一种树,每个结点有 |∑| 个儿子,每条边表示一个字符

空间 O(len) (如果假设 |∑| 为常数)

要判断某个串是否等于某个模式串,只要在 Trie 上走一遍(线性的)

在 Trie 上 KMP

实际上要做的事情是求出 Trie 的每个节点的 next

当然,这里的 next 不再是一个值,而是相当于是一个指针 —— 它可能指向其他分支的节点。

这时 next 的定义:最长的等于同长度的后缀的从根开始的路径的长度

求法跟 KMP 中的一样,只是要改成在 Trie 上 BFS

复杂度:均摊分析失效了,其实只能在每条链上均摊分析,于是总复杂度为模式串长总和


评论