algorithm - 三分探索木で最長の共通プレフィックスを見つける

Question

I implement a ternary search tree for a 20000 words.I want to know an algorithm to find a longest common prefix(prefix that is shared by at least 2 words)? Is there anyway to find a Longest Common Prefix in a tree?(without ternary search tree)

Answer 1

非常に簡単な解決策があり、それは線形の複雑さです。ご存じのように、Rabin-Karpは、ハッシュを使用してそれを行う文字列マッチング アルゴリズムです。アイデアは、ハッシュテーブルを作成することです。すべての単語を調べ、それぞれの長さ 1, 2, .. len( word ) でキー (その部分文字列のハッシュ値) を table に入れます。そのハッシュ値を持つ 2 つの単語 (少なくとも)。次に、そのプロパティを持つ最長のインデックスを見つけるだけで済みます。