string - 最长循环子串

Question

这是关于 Jon Bentley 的“Programming Pearls”中描述的最长循环子串算法的问题。我记得，他们为输入字符串构建一个后缀数组，对后缀进行排序，然后扫描它们。

看起来最昂贵的步骤是排序。如果我们使用比较排序，则比较次数为 O(N*logN)，其中 N 是输入字符串的大小。由于字符串比较是 O(string length)，所以排序是 O(N^2)。

有道理吗？

因此，该算法在空间上是 O(N^2) 和 O(N)。可以做得更好吗？

Answer 1

虽然您可以从后缀树构造后缀数组，但这样做没有什么意义。它将消除后缀数组的主要优势(除了一般的简单性之外):极小的内存消耗。

有一种简单的方法可以在 O(n*logn) 时间内对后缀数组进行排序。 (因此，它经常用于各种算法竞赛中，作为复杂后缀尝试的替代方法)

基本思路如下。我们将分阶段对后缀进行排序，在阶段 i (i = 0, 1, 2, 3, ...) 中仅第一个 2^i 考虑每个后缀的字符。

按第一个字符对后缀进行排序是微不足道的，对您来说应该没有问题。在这个(“第 0 个”)阶段之后，我们将得到部分排序的后缀数组和另一个数组，其中包含将后缀分区到桶中:每个桶都包含具有相同第一个符号的后缀。

现在，假设我们已经完成阶段 i 并现在处理阶段 i + 1。我们需要比较属于同一个桶的两个后缀s(t)和s(q)。 (让 s(t) 成为原始字符串中从位置 t 开始的后缀。)
由于前 2^i 个字符对它们来说是相同的，我们只需要考虑接下来的 2^i 个字符(因此，总数将是 2^( i+1)).但是没有第一个 2^i 符号的后缀 s(t) 是 s(t + 2^i)。因此，我们只需要根据s(t + 2^i)和s(q + 2^i)的第一个2^i进行比较code> 符号，我们已经从阶段 i 获得了这些信息。

结束。第一次实现它可能有点棘手(也是一个很好的练习)，但这就是想法。请注意，我们从原始字符串中读取实际字符的唯一时间是步骤 0。然后，在步骤 i 中，我们只使用步骤 i - 1 的结果。

编辑
This original paper from 1989以更多细节展示了这个想法。 (恕我直言，比理解它所需的更多细节和比需要更复杂的实现。)