라빈-카프 알고리즘(Rabin-Karp)은 롤링 해시(Rolling Hash) 를 이용해 문자열 패턴을 탐색하는 알고리즘이다. 텍스트의 부분 문자열 해시와 패턴 해시를 비교해 O(n+m) 평균 시간복잡도를 달성하며, 여러 패턴 동시 탐색에 특히 유리하다.
롤링 해시
창(window)을 오른쪽으로 한 칸 이동할 때 전체 재계산 없이 O(1)로 해시를 갱신한다.
해시 공식: H = (c1·d^(m-1) + c2·d^(m-2) + ... + cm) mod q
(d: 진법, q: 소수, ci: 문자 값)
슬라이딩 시:
새 해시 = (이전 해시 - c1·d^(m-1)) * d + c(m+1)
→ 덧셈/곱셈/나머지 연산만으로 O(1) 갱신
구현
python
def rabin_karp(text, pattern):
n, m = len(text), len(pattern)
d, q = 256, 101 # 진법, 소수 mod 값
h = pow(d, m-1, q) # d^(m-1) mod q
p_hash = 0
t_hash = 0
result = []
for i in range(m):
p_hash = (d * p_hash + ord(pattern[i])) % q
t_hash = (d * t_hash + ord(text[i])) % q
for i in range(n - m + 1):
if p_hash == t_hash:
# 해시 충돌 검사 — 실제 문자열 비교
if text[i:i+m] == pattern:
result.append(i)
if i < n - m:
# 롤링 해시 업데이트
t_hash = (d*(t_hash - ord(text[i])*h) + ord(text[i+m])) % q
if t_hash < 0:
t_hash += q
return result
해시 충돌 (Spurious Hit)
해시가 같아도 실제 문자열이 다를 수 있다 — 이를 위한 실제 비교가 필요하다. 좋은 해시 함수 선택으로 충돌 확률을 낮춘다.
여러 패턴 동시 탐색
패턴 해시를 집합(set)에 저장하면 k개 패턴을 O(n+m)에 동시 탐색 가능하다. KMP의 강점은 단일 패턴, 라빈-카프의 강점은 다중 패턴이다.
시간복잡도
| 케이스 | 복잡도 |
|---|
| 평균 | O(n + m) |
| 최악 (모든 해시 충돌) | O(nm) |
관련 개념
- •KMP 알고리즘 — 실패 함수 기반 선형 탐색
- •해시 — 라빈-카프의 핵심 도구
- •해시맵 — 해시 기반 자료구조
- •브루트 포스 — 단순 O(nm) 탐색
참고문헌
- •Rabin, M.O., Karp, R.M. (1987). Efficient Randomized Pattern-Matching Algorithms
