查找长度为N[关闭]的重复子字符串

Question

我必须制作一个Java程序，在给定字符串中找到长度为n的所有重复子字符串。输入是字符串是非常长的，一个暴力的方法需要太多的时间。

我已经尝试了:
现在，我将分别查找每个子字符串，并使用KMP alogrithm检查该子字符串的重复。这也太花时间了。

解决这个问题的更有效的方法是什么？

Answer 1

1）应该考虑使用后缀树数据结构。

后缀树

这个数据结构可以在O(N*logn)时间内构建
（我认为使用Ukkonen的算法甚至可以在O(N)时间内构建）
其中N是输入字符串的大小/长度。
然后它允许在O(M)时间内解决许多（否则）困难的
任务，其中M是模式的大小/长度。

所以即使我没有试过你的问题，我很肯定
如果你使用后缀树和你的问题的一个聪明的公式，那么
问题可以通过使用后缀树来解决（在合理的O时间内）。

2）关于这些（及相关）主题的一本很好的书是这本：

关于字符串、树和序列的算法

除非你在算法方面受过良好的训练，否则读起来并不容易。
但好吧，读这样的东西是获得良好训练的唯一方法；）

3）我建议你也看看这个算法。

Aho-Corasick算法

虽然，我不确定但是...这一个可能有点
离题与您的特定问题。