【UOJ35】后缀排序 Vol.2

用后缀自动机求后缀数组

\(O(n)\)即可,常数也不大,比倍增和DC3不知道高到哪里去了

首先我们需要一棵后缀树。后缀树直观地讲就是把一个串的所有后缀建一棵trie树,然后将只有一个儿子的点与它的儿子合并形成的树。

怎么建后缀树呢?其实很simple。

我们将这个串反过来建后缀自动机。那么实际上,\(fail\)树就是原串的后缀树。其实也很好理解:在后缀树中,每个叶子结点是一个后缀,每个点的父亲是它的前缀。而在\(fail\)树中,恰好有每个叶子结点是一个前缀,每个点的父亲是它的后缀。

得到了后缀树后,剩下的就很容易了。从根节点开始DFS,先走字母小的边,依次走到的所有后缀就对应了后缀数组。两个后缀的LCP即为它们LCA的深度(要考虑一条边的长度不一定为\(1\)),DFS时记录一下即可。

如何保证先走字母小的边并且复杂度不变?只需要知道每个点由父亲走来的第一个字母是什么,按照这个字母的顺序连边即可。

可以记录每个点\(right\)集合中的任意一个\(R_i\),那么那个字母就是\(s_{R_i-len_{fail_i}}\)。手画一下很容易验证这一点。

说点什么

您将是第一位评论人!

提醒
wpDiscuz