後綴樹：最長的重複子字符串實現

我已經實現了一個未壓縮的後綴樹。我想知道如何解決查找字符串中最長的表示子字符串的問題。我知道我們必須找到有兩個孩子的最深的內部節點，但是如何編碼呢？另外，我們如何知道最長的重複子字符串是什麼。我對JAVA中的代碼感興趣。請給java實現。作爲參考，我TrieNode看起來像後綴樹：最長的重複子字符串實現

class TrieNode{ 

char ch; 
LinkedList<TrieNode> child; 

}

來源

2010-12-18 TimeToCodeTheRoad

http://stackoverflow.com/a/24705760/69663給出了一種方法來過濾掉重疊（雖然它也過濾了一些字符串的全部等於字母） – unhammer 2016-12-26 08:36:28

的算法，這是隻有2個孩子最深的節點，如果你存儲字節的字符串的結束。

要找到最長的子字符串，你需要做一個depth first search，保留一個對具有2個或更多子元素的最深節點的引用，並且它是深度。這是遞歸函數最容易做到的。

來源

2010-12-18 19:11:46

正確，但這會給答案重疊允許。我的意思是字符串「香蕉」，答案是「ana」。我想重疊不允許。所以答案應該是「an」或「na」 – TimeToCodeTheRoad 2010-12-18 21:16:27

好吧，我不確定你的意思是重疊，也許不止一次使用1個字母？無論如何，如果您不想包含特定的字符串，那麼當您進行深度優先搜索時，只需排除不符合您的標準的節點。 – 2010-12-19 08:48:32

你可以通過在https://daniel-hug.github.io/longest-repeated-substring/中輸入「aaa」來看到重疊的問題 - 它聲稱「aa」是一個重複的子字符串，因爲在樹中[ （「$」，葉），（「A」，[（「$」，葉），（「A」，[（「$」，葉），（「A $」，葉）]）]）]' ，具有兩個葉子後代的最深節點具有前綴「aa」的路徑。 – unhammer 2016-12-17 10:24:19

Aho- Corasick http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

來源

2010-12-18 19:02:02

要找到最深的節點，還可以做BFS和選擇具有最高級別的節點。我認爲具有最高級別的節點也是最深的節點，然後可以檢查它是否有2個孩子。否則會更高。不知道這是否會工作。任何意見pps？

來源

2010-12-18 19:56:37 Programmer

後綴樹：最長的重複子字符串實現

回答

相關問題