Rabin-Karpアルゴリズムは、ハッシュ関数を使用してパターンとテキストの一部をハッシュ値に変換します。パターンのハッシュ値とテキスト内の各部分文字列のハッシュ値を比較することで、一致する箇所を見つけることができます。このアルゴリズムは、テキスト内のすべての部分文字列を総当たりで比較するBrute-Forceアルゴリズムよりも効率的です。
Rabin-Karpアルゴリズムの手順は次のとおりです:
- パターンとテキストのハッシュ値を計算します。
- ハッシュ値が一致する場合、パターンと部分文字列を比較します。
- ハッシュ値が一致しない場合、次の部分文字列のハッシュ値を計算します。
- テキストの終わりまで繰り返します。
Rabin-Karpアルゴリズムの利点は、ハッシュ値の計算が高速であり、テキスト内の部分文字列の一致を素早く見つけることができる点です。しかし、ハッシュ値の衝突や誤検出の可能性にも注意する必要があります。
以下に、Pythonで実装されたRabin-Karpアルゴリズムの簡単なコード例を示します:
def rabin_karp(pattern, text):
pattern_hash = hash(pattern)
pattern_length = len(pattern)
text_length = len(text)
for i in range(text_length - pattern_length + 1):
if hash(text[i:i+pattern_length]) == pattern_hash:
if text[i:i+pattern_length] == pattern:
return i
return -1
# 使用例
text = "This is a sample text for testing the Rabin-Karp algorithm."
pattern = "Rabin-Karp"
index = rabin_karp(pattern, text)
if index != -1:
print("Pattern found at index:", index)
else:
print("Pattern not found.")このコード例では、与えられたテキストとパターンを使ってrabin_karp関数を呼び出し、パターンの最初の出現インデックスを返します。もしパターンが見つからない場合は-1を返します。
以上が、Rabin-Karpアルゴリズムの簡単な解説とコード例です。このアルゴリズムは文字列検索やマッチングの問題において効率的な手法であり、多くの実用的な応用があります。