对于长度为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 值，它呈指数增长。
这个问题有更高效的算法吗？
最佳答案
后缀树解决此类问题的速度非常快，通常是 O(n) 的时间和空间。
查看维基页面:
并阅读该页面上链接到的 Material (功能部分):
关于algorithm - 出现n次的最长子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2575609/