algorithm - 从后缀数组制作 LCP

Question

我正在学习 Suffix 数组，并从本教程中成功学习了如何在 O(nlognlogn) 时间内制作 Suffix 数组。

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

我找不到任何好的在线资源请帮助我，这样我就可以完全学习这个主题，它会帮助其他人。

谢谢

Answer 1

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

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

正确（afaik）实施：https ://sites.google.com/site/indy256/algo/suffix_array

Answer 2

您可以使用 kasai 的算法在 O(n) 时间内从后缀数组制作 LCP 数组

从后缀数组构造 lcp 数组