从后缀数组生成LCP

Question

我正在学习后缀数组，并成功地从这个Tutorial中学会了如何在O(nlognlogn)时间内创建一个后缀数组。

现在我想知道如何在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数组

construction of lcp array from suffix array