6

この質問は単にアルゴリズムに関するものです。擬似コードでは次のようになります。

A = Array of strings; //let's say count(A)  = N
S = String to find;   //let's say length(S) = M

for (Index=0; Index<count(A); Index++)
  if (A[Index]==S) {
    print "First occurrence at index\x20"+Index;
    break;
  }

この for ループでは、N 回の文字列比較 (またはバイト比較 N*M 回、O(N*M)) が必要です。これは、配列 A に多数の項目がある場合、または文字列 S が長すぎる場合によくありません。

最初の出現を見つけるためのより良い方法はありますか? O(K*logK) の一部のアルゴリズムは問題ありませんが、O(K) が望ましいか、O(logK) が最適です。ここで、K は N または M のいずれかです。

他の構造を追加したり、比較ループの前にデータ処理を行ったりしてもかまいません。

4

5 に答える 5

4

文字列をハッシュベースのセットに入れ、セットが構築されると、特定の文字列がセットに含まれているかどうかをテストして、多かれ少なかれ一定のパフォーマンスが得られるようにします。

于 2012-04-28T18:40:46.877 に答える
4

文字列の配列全体を有限状態マシンに変換できます。遷移は文字列の文字であり、状態を生成した文字列の最小インデックスを状態に配置します。これには多くの時間がかかり、インデックス作成と見なされる場合があります。

于 2012-04-28T18:42:49.357 に答える
3

自己平衡二分探索木を使用できます。ほとんどの実装には、挿入するO（log（n））と、検索するO（log（n））があります。

セットがそれほど大きくなく、値に適したハッシュ関数がある場合は、ハッシュベースのセットの方が優れたソリューションです。その場合、挿入するO（1）と検索するO（1）が必要になるためです。ただし、ハッシュ関数が悪い場合やセットが大きすぎる場合は、挿入するのはO（n）、検索するのはO（n）になります。

于 2012-04-28T19:02:57.730 に答える
3

最初に文字列の配列を並べ替えることができますが、これには O(m*nlogn) 時間がかかります。A がソートされた後、線形検索の代わりに二分検索を実行できます。これにより、合計実行時間が O(m*logn) に短縮されます。

この方法の利点は、実装が非常に簡単なことです。たとえば、Java では、たった 2 行のコードでこれを行うことができます。

Arrays.sort(A);
int index = Arrays.binarySearch(A, "S");
于 2012-04-28T18:57:44.817 に答える
1

できるだけ速く検索するための最良の方法は、配列をソートすることです。説明したように、検索でいくつかのヒューリスティックまたは制約を可能にする可能性のある情報は事前にないようです。

最初に配列を並べ替え（たとえば、クイックソート、O（NlogN））、次にバイナリ検索を実行しますO（log（N））

于 2012-04-28T19:06:13.690 に答える