我为 20000 个单词实现了三元搜索树。我想知道一种算法来找到最长的公共前缀（至少由 2 个单词共享的前缀）？无论如何要在树中找到最长的公共前缀？（没有三元搜索树）
问问题
395 次
1 回答
2
有一个非常简单的解决方案，它是线性复杂度，你知道Rabin-Karp是一种字符串匹配算法，它使用散列来做到这一点。想法是创建一个哈希表。您遍历所有单词，并在每个长度 1、2、..len(word) 处将键（该子字符串的哈希值）放入表中，并且当表中已经有了该键时，这意味着您有具有该哈希值的 2 个单词（至少）。然后你只需要找到具有该属性的最长索引。
于 2013-02-11T21:40:48.507 回答