Rabin-Karp文字列検索アルゴリズムの原理と実装方法

1. 原理: Rabin-Karpアルゴリズムはハッシュ関数を利用して文字列の比較を行います。まず、パターンとテキストの最初の窓（パターンの長さと同じ長さの部分文字列）のハッシュ値を計算します。その後、窓を一つずつスライドさせながら、窓のハッシュ値とパターンのハッシュ値を比較します。ハッシュ値が一致した場合には、実際の文字列の比較を行い、一致しない場合は窓を次にスライドします。このアルゴリズムは、ハッシュ値の計算と比較を繰り返すことで、効率的に文字列の一致位置を見つけることができます。

2. 実装方法: 以下に、PythonでのRabin-Karpアルゴリズムの基本的な実装例を示します。

def rabin_karp(pattern, text):
    pattern_len = len(pattern)
    text_len = len(text)
    pattern_hash = hash(pattern)
    text_hash = hash(text[:pattern_len])
    for i in range(text_len - pattern_len + 1):
        if pattern_hash == text_hash and pattern == text[i:i+pattern_len]:
            return i
        if i < text_len - pattern_len:
            text_hash = hash(text[i+1:i+pattern_len+1])
    return -1
# 使用例
text = "This is a sample text"
pattern = "sample"
result = rabin_karp(pattern, text)
print("Pattern found at index:", result)

上記のコードでは、rabin_karp関数がパターンとテキストを受け取り、パターンがテキスト内で見つかった場合はそのインデックスを返します。見つからない場合は-1を返します。

このように、Rabin-Karpアルゴリズムを使うことで、大きなテキスト内での文字列の検索を効率的に行うことができます。

以上がRabin-Karp文字列検索アルゴリズムの原理と実装方法の説明です。ご参考になれば幸いです。