查找长度为N的重复子字符串

Question

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

我一直在尝试：
目前我正在分别查找每个子字符串，并使用KMP alogrithm检查该子字符串的重复。这也花了太多时间。

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

Answer 1

我要带@peter去。petrov的建议，并通过解释如何实际使用后缀树来解决问题来增强它：

 1. Create a suffix tree from the string, let it be `T`.
 2. Find all nodes of depth `n` in the tree, let that set of nodes be `S`. This can be done using DFS, for example.
 3. For each node `n` in `S`, do the following:
     3.1. Do a DFS, and count the number of terminals `n` leads to. Let this number be `count`
     3.2. If `count>1`, yield the substring that is related to `n` (the path from root to `n`), and `count`

请注意，该算法处理长度为n的任何子串，并将其添加到集合S，然后通过计算该子串所指向的终端数量，从那里搜索该子串的实际次数。

这意味着问题的复杂性是O（创建遍历）-意思是，您首先创建树，然后遍历它（很容易看出您不会在步骤2-3中遍历树中的每个节点不止一次）。由于遍历显然比创建树“更快”-它留给您O（创建），正如@perer.petrov所指出的，它是O（|S|）或O（|S|log|S|），这取决于您选择的算法。

Answer 2

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

后缀树

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

因此，尽管我没有尝试你的特定问题，但我非常确定，如果你使用后缀树和问题的智能公式，那么
问题可以通过使用后缀树（在合理的时间内）来解决。

这是一本关于这些（和相关）主题的非常好的书：

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

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

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

Aho-Corasick算法

尽管，我不确定，但是...关于你的特定问题，这可能有点离题。