Algorithm Guidecomplexity: 평균 O(n + m)

라빈-카프 (Rabin-Karp)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

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 Understand It Simply

For Everyone

🔑Analogy

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

💡In Plain Words

패턴과 텍스트 구간의 해시를 비교하고, 같을 때만 실제 글자를 확인합니다.

롤링 해시로 구간 해시를 O(1)에 갱신해 빠르게 훑어요.

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 라빈-카프 (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

04 Frequently Asked Questions

FAQ

What is 라빈-카프 (Rabin-Karp)?+

What is the time complexity of 라빈-카프 (Rabin-Karp)?+

The time complexity of 라빈-카프 (Rabin-Karp) is 평균 O(n + m). Follow the step-by-step visualization to see exactly why.

Where is 라빈-카프 (Rabin-Karp) used?+

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

What's a simple analogy for 라빈-카프 (Rabin-Karp)?+

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

→ Strings — see allRelated

🔤KMP 문자열 탐색 (Knuth-Morris-Pratt)

O(n + m)

🔤보이어-무어 (Boyer-Moore)

최선 O(n / m)

Guide Progress0%