-1

yという形式の長さ N の16 進文字列があるとしy{N}y{N-1}...y{1}ます。x次に、長さ L (L は N 未満) の別の 16 進文字列が与えられた場合、この文字列が内部に出現する回数 (存在する場合) を確認したいと思いyます ... のように言いy{N}...x{L}x{L-1}...x{1}...y{j}..x{L}x{L-1}...x{1}....y{1}ます。C++ でこれを行う最も効率的な方法はどれですか?...大規模なデータベースに対してこれを実行したいので、本当に効率的な実装が必要です

4

3 に答える 3

1

C++ でこれを行う最も効率的な方法はどれですか?

次のように、入力ファイルstd::search全体を試してください。std::istream_iterator

#include <string>
#include <iterator>
#include <iostream>
#include <algorithm>

int main () {
  // std::ifstream input("input.txt");
  std::istream& input(std::cin);
  std::string search_for("1234");

  std::istream_iterator<char> last;
  std::istream_iterator<char> it(input);
  int count(0);

  while((it = std::search(it, last, search_for.begin(), search_for.end())) != last) {
    count++;
  }

  std::cout << count << "\n";

}

それが十分に速くない場合は、試してみてくださいstd::istreambuf_iterator。

それが十分に高速でない場合は、ファイルをメモリ マップし、イニシャル ポインターとファイナル ポインターを反復子として使用してみてください。

于 2012-09-24T15:10:28.530 に答える
1

リクエストは単純な文字列検索アルゴリズムです。それを行うアルゴリズムはたくさんあります。それらのほとんどは、前処理を使用して O(L+N) で適切な回答を提供します。

O(L + Z) でより高速な答えを提供するサフィックス ツリーを使用することもできます。ここで、Z は y 内の x の出現回数です。サフィックス ツリーは多くのメモリ空間 (O(N²)) を必要としますが、ここでは理想的な選択ではないかもしれません。

于 2012-09-24T11:19:12.707 に答える
1

「16 進数」は、ここでは意味がありません。C++ はコンピューター言語であり、ビットで動作します。「16 進数」は、人間が消費するために 4 ビットをグループ化するための便利な方法です。

同様に、C++ は のような文字列にインデックスを付けませんy{N}y{N-1}...y{1}。として索引付けしますy[0],y[1],y[N-1]。（ありませんy[N]。）

通常の状況でstd::string::findは、ディスクよりも高速になります。つまり、十分に高速です。

于 2012-09-24T11:20:42.327 に答える