python - 查找字符串中最长的重复序列

Question

我需要在字符串中找到最长的序列，并注意该序列必须重复三次或更多次。因此，例如，如果我的字符串是:

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

那么我希望返回值“helloworld”。

我知道有几种方法可以做到这一点，但我面临的问题是实际的字符串大得离谱，所以我真的在寻找一种可以及时完成的​​方法。

Answer 1

这个问题是 longest repeated substring problem 的变体。并且有一个 O(n) 时间算法来解决它，它使用 suffix trees .这个想法(正如维基百科所建议的)是构建一个后缀树(时间 O(n))，用后代的数量(时间 O(n) 使用 DFS)注释树中的所有节点，然后找到具有至少三个后代的树中最深的节点(使用 DFS 的时间 O(n))。这个整体算法需要时间 O(n)。

也就是说，众所周知，后缀树很难构建，因此在尝试此实现之前，您可能希望找到一个为您实现后缀树的 Python 库。快速谷歌搜索出现this library ，虽然我不确定这是否是一个好的实现。

另一种选择是使用 suffix arrays结合 LCP arrays .您可以遍历 LCP 数组中的相邻元素对，取每对元素中的最小值，然后以这种方式存储您找到的最大数字。这将对应于重复至少 3 次的最长字符串的长度，然后您可以从那里读取字符串本身。

有几种简单的算法可用于构建后缀数组(Manber-Myers 算法运行时间为 O(n log n)，而且编写起来并不难)，而 Kasai 的算法构建 LCP 数组的时间为 O(n)并且编码起来相当简单。

希望这会有所帮助!