algorithm - 从后缀数组制作 LCP

Question

我正在学习后缀数组，并且成功地学习了如何在 O(nlognlogn) 时间内制作后缀数组来自这个 Tutorial .

现在我想知道如何在 O(nlogn) 时间或更好的时间内从我的后缀数组创建 LCP 数组，显然我知道 O(n*n) 方法。我想要更好的东西

我找不到任何好的在线资源请帮助我，这样我才能完全学习这个主题，这会对其他人有所帮助。

谢谢

Answer 1

最简单的 O(n) 方法是从左到右(最长到最短)后缀循环。然后注意，如果排序后缀数组表中 i 处的当前后缀与其邻居之间的最长公共(public)前缀(LCP)为 h，则 i + 1 处的下一个 LCP 最多可以减少一个。这是因为下一个后缀相当于将第一个字符向前推进一个字符，因此我们至少可以通过将邻居也向前推进一个字符来实现 h - 1。如果不同的后缀恰好介于两者之间，它仍将共享至少 h - 1 的前缀。

这允许我们通过尽可能向前推进，然后在移动到下一个索引时向前推进一个 O(n) 摊销算法。

正确的(afaik)实现:https://sites.google.com/site/indy256/algo/suffix_array