查找長度爲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|)，具體取決於您選擇的算法。