最长的非重叠子串

Question

我想知道是否有人知道最长重复非重叠子串的(最佳？)算法.

例如,在字符串中

ABADZEDGBADEZ

最长的反复出现是"不好".顺便提一下,如果没有这样的结果,算法应该警告这样的事情已经发生.我猜这是涉及后缀树.

我敢肯定这已经存在了.谢谢您的帮助!

Answer 1

后缀数组是解决这个问题的一个很好的数据结构。

在Jon Bentley 的Programming Pearls 中有一个解决这个问题的方法。

Answer 2

由于您要将其应用于音乐，因此您可能不会寻找 100% 的匹配；而是会寻找 100% 的匹配。主题的一个实例与另一个实例之间可能存在预期差异。您可以尝试查找基因序列分析算法 - 那里有很多这样的东西。尝试 BLAST 或其他对齐算法。

您还可以尝试 WinEPI 系列算法，以及此特定结果集的各种前缀树实现（这些结果允许子字符串中存在间隙；例如，ABCID 和 AFBCD 都包含 ABCD）。实际上我有一篇关于算法的论文，如果你感兴趣的话可能值得一看；我需要获得分发授权，所以请告诉我。

请注意，对于大型数据集来说，这实际上是一个非常复杂的主题（要有效地完成）。

资料来源：对类似（主题检测）主题进行一两年的研究。