Algorithm Guidecomplexity: 평균 O(n + m)

라빈-카프 (Rabin-Karp)

패턴과 텍스트 구간의 해시값을 비교하는 문자열 탐색입니다. 롤링 해시로 구간 해시를 O(1)에 갱신하며, 해시가 같을 때만 실제 문자를 확인해 다중 패턴 검색에 유리합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Rabin-Karp · "CAB"

text

pattern

라빈-카프 시작. 패턴과 텍스트 구간의 '해시값'을 비교해 빠르게 후보를 거릅니다.

Logic Node1 / 8

Live Python

1def rabin_karp(text, pattern):

2 m = len(pattern)

3 p_hash = hash_of(pattern) # 패턴 해시 미리 계산

4 win_hash = hash_of(text[:m])

5 for i in range(len(text) - m + 1):

6 if win_hash == p_hash: # 해시가 같으면

7 if text[i:i+m] == pattern: # 실제 문자 확인

8 return i

9 win_hash = roll(win_hash, text, i, m) # O(1) 롤링 갱신

10 return -1

02 쉽게 이해하기

For Everyone

🔑비유

책을 일일이 안 읽고 바코드(해시)만 먼저 대조해 후보를 거르는 것과 같습니다.

💡쉽게 말하면

패턴과 텍스트 구간의 해시를 비교하고, 같을 때만 실제 글자를 확인합니다. 롤링 해시로 구간 해시를 O(1)에 갱신해 빠르게 훑어요.

📍어디에 쓰나

표절·중복 문서 검사, 다중 패턴 검색.

03 파이썬 구현 코드

라빈-카프 (Rabin-Karp)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    n, m = len(text), len(pattern)
    if m > n:
        return -1
    high = pow(base, m - 1, mod)
    p_hash = t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if p_hash == t_hash and text[i:i + m] == pattern:
            return i
        if i < n - m:
            t_hash = ((t_hash - ord(text[i]) * high) * base
                      + ord(text[i + m])) % mod
    return -1

Guide Progress0%