查找三元搜索樹中最長的公共前綴

Question

我爲20000個字實現了一個三元搜索樹。我想知道一個算法來查找最長的公共前綴（前綴至少由2個字共享）？ 反正有沒有找到一個最長公共前綴在一棵樹上？（不包括三元搜索樹）

Answer 1

有一個非常簡單的解決方案，它是線性複雜，你知道 Rabin-Karp是使用散列做一個字符串匹配算法那。 ideea是創建一個哈希表。你閱讀所有的單詞，並在每一個長度1，2，... len（單詞）你把密鑰（該子字符串的哈希值）在表中，當你已經在表中有這個密鑰，這意味着你有2個字（至少）與該散列值。那麼你只需要找到具有該屬性的最長索引。