ラビン・カープアルゴリズムとは何ですか?

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

このアルゴリズムはハッシュ技術を利用して、パターンのハッシュ値とテキストの部分文字列を比較します。次のように動作します。

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

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

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

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

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

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

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

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

";
      }

      // Calculate the hash value for the next window of text
      if ($i 

出力

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

コードの説明

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

結論

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