Rabin-Karpアルゴリズム:文字列検索の効率的な手法

パターンとテキストの長さを取得します。
パターンとテキストの初期ハッシュ値を計算します。
パターンとテキストのハッシュ値を比較し、一致するかどうかを確認します。
パターンとテキストのハッシュ値が一致する場合、実際に文字列を比較して一致を確認します。
一致した場合、パターンの出現位置を記録します。
テキスト内の次の部分文字列に進み、ハッシュ値を更新します。
テキストの終端まで上記の手順を繰り返します。

以下に、PythonでのRabin-Karpアルゴリズムの実装例を示します。

def rabin_karp(pattern, text):
    m = len(pattern)
    n = len(text)
    pattern_hash = hash(pattern)
    text_hash = hash(text[:m])

    for i in range(n - m + 1):
        if pattern_hash == text_hash:
            if pattern == text[i:i+m]:
                print("Pattern found at index", i)
        if i < n - m:
            text_hash = hash(text[i+1:i+m+1])

上記の実装では、hash()関数は単純なハッシュ関数として使用されていますが、実際のアプリケーションではより複雑なハッシュ関数を使用することが推奨されます。

これで、Rabin-Karpアルゴリズムを使用して文字列の検索を効率的に行う方法を学びました。このアルゴリズムは、大量のテキストデータやパターンマッチングが必要な場合に特に有用です。