查找长度N的重复子字符串
我必须制作一个Java程序，它可以查找给定字符串中所有重复的长度为n的子字符串。 输入的字符串非常长，而暴力方法需要太多时间。
我试过了：
目前，我正在分别查找每个子字符串，并使用KMP算法检查该子字符串的重复。 这也需要太多时间。
什么是更有效的方法来解决这个问题？
1）你应该看看使用后缀树数据结构。
后缀树
这个数据结构可以在O（N * log N）时间内建立
（即使在使用Ukkonen算法的O（N）时间，我也认为）
其中N是输入字符串的大小/长度。
然后它允许解决许多（否则）困难
O（M）时间中的任务，其中M是模式的大小/长度。
所以，即使我没有尝试你的特定问题，我很确定这一点
如果你使用后缀树和你的问题的智能公式，那么
问题可以通过使用后缀树来解决（在合理的O时间内）。
2）关于这些（和相关）主题的非常好的书是这样的：
字符串，树和序列的算法
除非你的算法训练有素，否则阅读起来并不容易。
但是，好的，阅读这些东西是获得良好训练的唯一途径;）
3）我建议你也快速浏览一下这个算法。
Aho-Corasick算法
尽管如此，我不确定但是......这个可能有点
关于你的特定问题的话题。
我将采取@ 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|)取决于你选择的算法。