我为 20000 个单词实现了一个三元搜索树。我想知道一种算法来找到最长的公共(public)前缀(由至少 2 个单词共享的前缀)？ 有没有办法在树中找到最长公共(public)前缀？(没有三元搜索树)
最佳答案
有一个非常简单的解决方案，它是线性复杂度，你知道 Rabin-Karp是一种字符串匹配算法，它使用散列来做到这一点。想法是创建一个哈希表。您遍历所有单词，并在每个长度为 1、2、..len(word) 时将键(该子字符串的哈希值)放入表中，当您已经在表中拥有该键时，这意味着您有具有该哈希值的 2 个单词(至少)。然后你只需要找到具有该属性的最长索引。
关于algorithm - 在三元搜索树中查找最长公共(public)前缀，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14800267/