Rabin-Karp アルゴリズムを使用したパターン検索のための PHP プログラム

Rabin-Karp アルゴリズムとは何ですか?

Rabin-Karp アルゴリズムは、大きなテキスト内のパターンの出現を効率的に検索する文字列パターン マッチング アルゴリズムです。 1987 年に Michael O. Rabin と Richard M. Karp によって開発されました。

このアルゴリズムは、ハッシュ技術を利用して、パターンのハッシュ値とテキスト部分文字列を比較します。仕組みは次のとおりです。

• パターンとテキストの最初のウィンドウのハッシュ値を計算します。

• パターンをテキスト上で一度に 1 位置ずつスライドさせ、ハッシュを比較します。

• ハッシュが一致する場合は、パターンの文字と現在のテキスト ウィンドウを比較して一致を確認します。

• 一致する場合は、一致する位置/インデックスを記録します。

• ローリング ハッシュ関数を使用して、次のテキスト ウィンドウのハッシュ値を計算します。

• テキストのすべての位置を確認するまで、手順 3 ～ 5 を繰り返します。

ローリング ハッシュ関数は、前のウィンドウの最初の文字の寄与を減算し、新しいウィンドウの次の文字の寄与を加算することにより、新しいウィンドウごとにハッシュ値を効果的に更新します。これにより、ウィンドウごとにハッシュを最初から再計算する必要がなくなり、アルゴリズムがより効率的になります。

パターン検索用の Rabin-Karp アルゴリズム用の PHP プログラム

コードの説明

PHP コードは、パターン検索用の Rabin-Karp アルゴリズムを実装しています。パターンとテキストを入力として受け取り、テキスト内でパターンの出現を検索します。このアルゴリズムは、パターンとテキストの最初のウィンドウのハッシュ値を計算します。次に、テキスト上でパターンをスライドさせ、現在のウィンドウのハッシュとパターンを比較します。ハッシュが一致する場合、文字はさらに 1 つずつ検証されます。一致するものが見つかった場合は、パターンが見つかったインデックスを出力します。このアルゴリズムはローリング ハッシュ関数を使用して、各ウィンドウのハッシュ値を効率的に更新します。このコードは、テキスト「ABCABCABCABCABC」内でパターン「BC」を検索することによるアルゴリズムの使用法を示しています。

要約すると、PHP プログラムは、パターン検索用の Rabin-Karp アルゴリズムを効果的に実装しています。ローリング ハッシュ関数を利用し、ハッシュ値を比較することにより、このアルゴリズムは、より大きなテキスト内のパターンの出現を効率的に検索できます。プログラムはテキスト内で見つかったパターンのインデックスを正確に識別し、結果を出力します。このプログラムは、明確な構造と適切なハッシュ計算により、PHP でのパターン検索における Rabin-Karp アルゴリズムの能力と有用性を示しています。

以上がRabin-Karp アルゴリズムを使用したパターン検索のための PHP プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。