問題タブ [boyer-moore]

ファイルパスなどの非常に長い文字列があり、その中で何かを検索したいとします。たとえば、$ findコマンドのようなもの。これの基本的な実装は次のようになります。

それを行うこととBoyer Mooreのようなことの間にパフォーマンスの違いはありますか? それともstrstr、同じくらい効率的なことをすでに行っていますか?

基本的に、私は約10億の非常に長い文字列を持っており、最も効率的な部分文字列の実装に基づいて、それらを（インデックスなしで）高速に検索しようとしています。何を使えばいいですか？

更新: より具体的な例を挙げるために、検索したいファイルパスが 10 億あるとします。

そして、これから 1 つ以上の文字列を検索します。サンプルの例は次のとおりです。

以下は、Boyer-Moore 文字列マッチング アルゴリズムの擬似コードです。疑似コードはこのサイトから来ています。

last[T[i]]私の質問は、上記の疑似コードの 12 行目に示されているように、に 1 を追加する理由は何ですか?

Boyer Moore を実装する必要がありますが、最も適切なオカレンスを見つけなければなりません。（つまり、ボイヤー・ムーアの逆バージョン）。テキスト内でパターンが出現する右端の位置のインデックスを返します。* の検索は、テキストの右端側から始まり、最初の文字 (左側) まで進みます。for ループを逆にして発生回数をカウントしようとしましたが、コードはまだ正しく動作しません。正しい方向にシフトしないと思いますが、よくわかりません。これは私のコードです:

}