インデックス付き文字列のリストでhwの部分文字列を検索しますか？

Question

私はkeyが文字列keyword.supposeである辞書を実装しています。私は辞書に次のキーを持っています。私は、単一のキーワードは私がすべてたいほんを検索していた場合、それは一定のtime.butでそれを検索しますmathonとしserach場合

マット本町 は今ほん

LAT ほん が座っていましたgoogle searchの場合のように、一定の時間または最小限の時間にretreivedする3つの言葉のうちの何が私のアプローチですか？ は、目的のための辞書権利データ構造ですか？

辞書の値は、私がユーザに表示する必要がある項目のリストであり、検索は複数のキーワードに基づいています。

Answer 1

gaddagは、this paperに記載されているように、おそらく最善の策です。これは、単語のどこでも検索を開始し、前後に歩くことができるトライの変形です。それはO（1）ルックアップではありませんが、かなり速く、妥当なスペース使用量を持っています。

編集：複数のキーワードの場合は、各キーワードを個別に検索して、次に設定された交差点または結合を行います。あなたが思っているより速いでしょう。最も単純なアルゴリズムとして実装する価値があり、プロファイリング時に実際のボトルネックになっていることが判明した場合にのみ廃棄します。