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

Question

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

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

Answer 1

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

现在您需要能够找到从窗口中的指针开始的所有子串共享的公共(public)前缀的长度。这应该是窗口中指针之间出现的最小 LCP 值。如果您使用红黑树，例如 Java Treeset，其键由 LCP 值组成，作为最重要的组成部分，而一些决胜局(例如指针本身)作为次要组成部分，那么您可以保持最小值窗口内的 LCP 值以每次窗口调整粗略记录窗口大小为代价。