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

Question

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

我alread尝试：
目前我单独找到每个子字符串，并检查使用KMP alogrithm该子串的重复。这也需要太多时间。

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

Answer 1

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

Suffix Tree

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

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

2）本非常好的书对这些（以及相关的）对象是这个：

Algorithms on Strings, Trees and Sequences

这不是真的很容易，虽然阅读，除非你在算法训练有素。
但是好的，阅读这些东西是获得良好训练的唯一方法;）

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

Aho-Corasick Algorithm

虽然，我不知道，但...这一个可能有点
题外话针对您的具体问题。

Answer 2

我要带@ 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(Creation + Traversal) - 意思是说，您首先创建树，然后遍历树（很容易看到您不会遍历树中的每个节点2-3次以上） 。由于遍历显然比创建树更“快”，因此它会留下O(Creation)，正如@ perer.petrov指出的那样，它是O(|S|)或O(|S|log|S|)，具体取决于您选择的算法。