c++ - LCS 的后缀树与后缀数组

Question

我正在开发一个程序来查找多个字符串之间最长的公共子字符串。我已经降低了使用后缀数组或后缀树的方法。我想看看哪种方法更好（如果有的话）以及为什么。同样对于后缀数组，我已经看到了一些针对两个字符串的算法，但对于两个以上的字符串却没有。任何可靠的例子将不胜感激，再次感谢您的建议！

注意：我没有看到任何其他专门解决此问题的问题，但如果存在，请指出我的方向！

Answer 1

如果您有一个出现在所有序列中的子字符串，那么在后缀数组中，指向该子字符串每次出现的指针必须排列在一起。因此，您可以尝试通过沿 suffix 数组移动一个窗口来找到它们，该窗口的大小刚好足以包含每个序列的至少一次出现。您可以通过维护一个表格来在线性时间内完成此操作，该表格告诉您对于每个序列，该序列在该窗口内出现了多少次。然后，当您向前移动窗口的后端时，减少与您刚刚跳过的指针相关联的序列的计数，如有必要，将窗口的前端移动到足够远以拾取该序列的新出现并更新表格。

现在您需要能够找到从窗口中的指针开始的所有子字符串共享的公共前缀的长度。这应该是窗口中指针之间出现的最小 LCP 值。如果您使用红黑树，例如 Java Treeset，其键由 LCP 值作为最重要的组件和一些决胜局（例如指针本身）作为不太重要的组件组成，那么您可以保持最小值窗口内的 LCP 值，代价是每次窗口调整的大致日志窗口大小。