라빈-칼프(Rabin-Karp) 알고리즘은 문자열 검색(또는 문자열 매칭) 문제를 해결하기 위한 알고리즘 중 하나입니다. 이 알고리즘은 특히 여러 개의 패턴을 동시에 검색할 때 효과적입니다. 라빈-칼프 알고리즘의 핵심 아이디어는 '해싱'입니다. 해싱을 통해 문자열의 서브스트링(substring)에 대한 '지문(fingerprint)'을 빠르게 생성하고, 이 지문을 이용하여 매칭 여부를 확인합니다.
기본 아이디어
- 패턴 문자열(pattern)의 해시 값을 계산
- 텍스트 문자열(text)에서 패턴의 길이와 같은 크기의 첫 번째 서브스트링의 해시 값을 계산합니다.
- 두 해시 값이 같은지 비교합니다. 같다면, 해당 위치에서 문자 하나하나를 직접 비교하여 실제로 같은지 확인합니다.e
- 텍스트 문자열을 한 칸씩 이동하면서, 새로운 서브스트링의 해시 값을 계산하고 3번 과정을 반복합니다.
def rabin_karp(text, patterns):
# This function searches for patterns in the given text using Rabin-Karp algorithm.
# Prime number and base used for rolling hash computation
prime = 101
base = 256
# Helper function to calculate hash value
def hash_func(s, length):
h = 0
for i in range(length):
h = (h * base + ord(s[i])) % prime
return h
# Store length of longest pattern for window size
max_len = max(len(p) for p in patterns)
# Precompute hashes for patterns
pattern_hashes = {pattern: hash_func(pattern, len(pattern)) for pattern in patterns}
text_hash = hash_func(text, max_len)
# Store the result
result = []
for i in range(len(text) - max_len + 1):
# Check if hash of current text window matches any pattern hash
if text_hash in pattern_hashes.values():
# Check each pattern to see if it really matches
for pattern in patterns:
if text_hash == pattern_hashes[pattern]:
if text[i:i+len(pattern)] == pattern:
result.append((i, pattern))
# Calculate hash for next window (if not at the end)
if i < len(text) - max_len:
next_char = text[i + max_len]
text_hash = (text_hash - ord(text[i]) * pow(base, max_len - 1)) * base + ord(next_char)
text_hash %= prime
return result
# Example usage
text = "this is a test text"
patterns = ["test", "is"]
matches = rabin_karp(text, patterns)
print("Matches found:", matches)