入力: 文字列の配列と単一の文字列。
タスク: エントリの部分文字列が入力文字列と一致する配列内のすべてのエントリを検索します。
入力配列は、必要に応じて任意の方法で準備またはソートでき、必要な補助データ構造を構築できます。データ構造の準備に必要な時間は (健全な範囲内で) 重要ではありません。
目標は、検索の最大速度です。
単なる線形検索ではない、どのアルゴリズムを使用しますか?
質問する
77 次
2 に答える
0
すべての文字列サフィックスのインデックスを作成したい場合があります。サフィックスツリーを調べて、これを行う方法を見つけてください。ウィキペディアの記事は一般化しすぎている可能性があるため、適応したアルゴリズムを次に示します。
建物指数
- 配列内の各文字列
- すべてのサフィックスを取得し (長さ N の文字列には N 個のサフィックスがあります)、文字列への参照を順序付き連想コンテナーに格納します (OrderedMap> (index)
検索中
- インデックスで検索語の下限を見つける
- インデックス キーが検索語の前に付けられなくなるまで、下限から開始してインデックスを移動します。
- 見つかったすべての参考文献の合計が検索結果です
長さ N の文字列には N²/2 個の部分文字列がありますが、接尾辞は N 個しかありません。したがって、接尾辞ベースのデータ構造は、部分文字列ベースよりもメモリ効率が高くなるはずです。
于 2013-10-17T02:30:38.180 に答える
0
データ構造を準備するのにかかる時間は重要ではないと書かれているので、ハッシュ化します。キーは文字列 (具体的には部分文字列) であり、値は要素がキーを部分文字列として持つ配列内のインデックスに対応する整数のリストです。
構築するには、配列内の各文字列を取得し、その文字列のすべての可能な部分文字列を決定し、そのようなキーと値のペアをそれぞれハッシュ テーブルに挿入します。キーが既に存在する場合は、新しいリストを挿入/作成するのではなく、インデックスをリストに追加します。
このハッシュ テーブルを作成したら、O(1) が入力文字列に基づいてリストを取得して返すのと同じくらい簡単です。
編集:質問を詳しく見てみると、インデックスではなく、配列内の実際の文字列を返したいようです。ハッシュ テーブル アプローチはどちらの方法でも機能します。
于 2013-10-17T01:57:02.937 に答える