java - 查找长度为 N 的重复子串

Question

我必须编写一个 Java 程序来查找给定字符串中所有长度为 n 的重复子字符串。输入的字符串非常长，蛮力方法需要太多时间。

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

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

Answer 1

1) 你应该看看使用后缀树数据结构。

Suffix Tree

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

所以即使我没有尝试你的特定问题，我也很确定
如果您使用后缀树和问题的智能公式，那么
问题可以通过使用后缀树来解决(在合理的 O 时间内)。

2) 关于这些(和相关)主题的一本非常好的书是这本:

Algorithms on Strings, Trees and Sequences

不过，除非您受过良好的算法训练，否则阅读起来并不容易。
但是好吧，阅读这些东西是获得良好训练的唯一途径；)

3) 我建议您也快速浏览一下这个算法。

Aho-Corasick Algorithm

虽然，我不确定但是...这个可能有点
关于您的特定问题的题外话。