查找三元搜索树中最长的公共前缀

Question

我为20000个字实现了一个三元搜索树。我想知道一个算法来查找最长的公共前缀（前缀至少由2个字共享）？ 反正有没有找到一个最长公共前缀在一棵树上？（不包括三元搜索树）

Answer 1

有一个非常简单的解决方案，它是线性复杂，你知道 Rabin-Karp是使用散列做一个字符串匹配算法那。 ideea是创建一个哈希表。你阅读所有的单词，并在每一个长度1，2，... len（单词）你把密钥（该子字符串的哈希值）在表中，当你已经在表中有这个密钥，这意味着你有2个字（至少）与该散列值。那么你只需要找到具有该属性的最长索引。