"GetAllWithPrefix"を高速で実行できる膨大な量のレコードのデータ構造

Question

stringの長さが10000文字までの大量の値（〜10Mレコード）を格納するにはメモリ内のデータ構造が必要です助けになる）。

私は広範囲に次の操作を実行するつもりです：

1. は
2. GetAllWithPrefix（文字列のプレフィックス）を取り外し
3. を取得
4. を追加 - プレフィックスに対応するすべての値のリストを返します。

明らかに、上記の操作のいずれかが、私は少し錆びてるO(1)またはO(logn)

で行われる必要があります。そのための最良のデータ構造は何でしょうか？私は正しいクラスに向けるのが望ましい。

は何をしたい

Answer 1

は、各ノードは、ノードへの文字のマップ（枝）を有し、トライでの散歩は、プレフィックス徒歩木でトライ、である、特定のノードにも持っていただき、ありがとうございますこれは、たとえノードから別の枝が存在するとしても、トライに格納されている文字列の終わりにあるかどうかを示すフラグです（文字列は追加された別の文字列の接頭辞です）。 O（w）、lookupはO（w）であり、接頭辞検索はO（w + n）であり、wは文字列の長さであり、nはツリー内の語の総数であり、wは接頭辞である。

あなたがここに

https://visualstudiomagazine.com/articles/2015/10/20/text-pattern-search-trie-class-net.aspx?m=1

約1つのC＃実装を読むことができます更新 私はあなたの特別なケースでは上記の時間複雑さは、実際には、あなたの文字列の長さを考慮したときにO（1）持っていることを明確にしたいです上限は100です。