Oh My Algorithm
Algorithm Guidecomplexity: 평균 O(n + m)

라빈-카프 (Rabin-Karp)

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

01라빈-카프 (Rabin-Karp)

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

패턴 'CAB'의 해시를 미리 계산합니다 (= 17이라고 하죠).

윈도우 [0,2] 'ABA'의 해시는 31. 17과 다르므로 실제 문자는 보지도 않고 건너뜁니다.

롤링 해시로 다음 윈도우 [1,3] 'BAC'의 해시를 O(1)에 갱신 = 22. 여전히 다릅니다.

윈도우 [2,4] 'ACA' 해시 = 19. 또 다릅니다.

윈도우 [3,5] 'CAB' 해시 = 17. 패턴 해시와 일치! 이제 실제 문자를 확인합니다.

문자 'CAB'가 패턴과 정확히 같습니다(해시 충돌 아님). 인덱스 3에서 발견!

롤링 해시로 윈도우 해시를 O(1)에 갱신해, 평균 O(n+m)에 매칭합니다.

text
A
B
A
C
A
B
C
A
B
pattern
1 / 8

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

04 자주 묻는 질문

FAQ
라빈-카프 (Rabin-Karp)란 무엇인가요?+

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

라빈-카프 (Rabin-Karp)의 시간복잡도는 어떻게 되나요?+

라빈-카프 (Rabin-Karp)의 시간복잡도는 평균 O(n + m) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

라빈-카프 (Rabin-Karp)은(는) 어디에 사용하나요?+

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

라빈-카프 (Rabin-Karp)를 쉽게 비유하면?+

패턴과 본문 구간의 해시를 먼저 견주고 같을 때만 실제 문자를 확인합니다. 구간을 한 칸 옮길 때 해시를 처음부터 다시 계산하지 않습니다.

→ 문자열 전체 보기Related
🔤KMP 문자열 탐색 (Knuth-Morris-Pratt)
O(n + m)
🔤보이어-무어 (Boyer-Moore)
최선 O(n / m)