algorithm - 出现n次的最长子串

Question

对于长度为L的字符串，我想找到在该字符串中出现n(n 次或更多次的最长子串。

例如，在“BANANA”中出现 2 次或更多次的最长子串是“ANA”，一次从索引 1 开始，再次从索引 3 开始。子串允许重叠。

在字符串“FFFFFF”中，出现3次及以上的最长字符串是“FFFF”。

n=2 的强力算法将选择字符串中的所有索引对，然后一直运行直到字符不同。 running-along 部分需要 O(L) 并且对的数量是 O(L^2) (不允许重复，但我忽略了这一点)所以对于 n=2，此算法的复杂度为 O(L^3)。对于更大的 n 值，它呈指数增长。

这个问题有更高效的算法吗？

Answer 1

后缀树解决此类问题的速度非常快，通常是 O(n) 的时间和空间。

查看维基页面:

Suffix Trees .

并阅读该页面上链接到的 Material (功能部分):

Longest Repeated Substring .