使用Trie找到最長的公共子串

Question

如何在使用trie的兩個或更多個字符串中找到LCS（最長公共子串）？

我有個想法 - 假設我的第一個字符串是「abbcabdd」。 然後我會首先在trie中插入「abbcabdd」，然後是「bbcabdd」，然後是「bcabdd」....然後是「d」 並對每個字符串重複此過程。

然後通過遍歷trie來計算最長的子字符串。

但我認爲效率不高。 有沒有其他改進方法？

Answer 1

您所描述的內容正好是suffix tree - 使用經過優化的算法生成後綴樹，您將提高效率！

請注意，在O(n)中有一個用於構建後綴樹的算法（當然假設是一個常量字母表）。