prefix-tree - これのデータ構造は何ですか？

Question

任意の長さと数のバイナリ文字列のセット（重複なし）が与えられ、他の文字列のプレフィックスである文字列があるかどうかを調べる必要があります。小さなセットと長さの短い文字列の場合は簡単です。各文字列を読み取ってバイナリ ツリーを構築するだけで、プレフィックスの一致が見つかったときに完了します。ただし、長さが長い文字列が多数ある場合、この方法は効率的ではありません。 . これに適したデータ構造とアルゴリズムは何だろうと思っているだけです。ハフマンツリー？試行 (基数ツリー)? または何か？ありがとう。

Answer 1

私は試しに行きます。トライを使用して、各文字列の最後のノードがフラグでマークされるように、すべての文字列を挿入します。次に、各文字列について、そのパスに沿って進み、ページ上のいずれかのノードにフラグが設定されているかどうかを確認します。はいの場合、そのノードで終わる文字列は、分析している文字列のプレフィックスです。

n = 文字列の数、k = 平均長と仮定すると、両方を挿入して分析すると、合計で O(kn) かかります。

プレフィックス ツリー (ノードが 1 文字より長いトライ) の方が効率的かもしれませんが、実装は簡単ではありません。