라빈-카프 알고리즘 (Rabin-Karp)

정의

라빈-카프 (Rabin-Karp) 는 롤링 해시 (rolling hash) 를 이용해 패턴 문자열 P[0..M-1] 이 텍스트 T[0..N-1] 의 어디에 등장하는지 찾는 문자열 매칭 알고리즘. 1987 년 Rabin, Karp 가 고안. 평균 O(N + M), 최악 O(NM) 이지만 실제로는 충돌이 거의 없어 매우 빠르다.

문제 상황과 동기

길이 M 패턴이 길이 N 텍스트의 어디에 나타나는가?

• naive: 모든 위치에서 M 글자 비교. O(NM). N=10^6, M=10^5 면 10^11 연산.
• KMP/Z: O(N + M) 보장, 하지만 전처리 복잡.
• Rabin-Karp: 해시 함수 H(s) 로 패턴 해시 H(P) 를 계산 → 텍스트의 모든 M 길이 부분 문자열 해시를 O(1) 롤링 갱신. 해시 일치 시 실제 비교.

핵심 통찰: “슬라이딩 윈도우” 의 해시를 O(1) 에 갱신. polynomial hash → 첫 문자 빼고 뒤 문자 추가 → modulo 상수 시간.

자주 등장: 다중 패턴 매칭, 2D 패턴 (이미지 검색), plagiarism 검출.

시각화

핵심 아이디어

문자열 s[i..i+M-1] 의 해시를 다항식으로 정의:

H(s[i..i+M-1]) = (s[i]·B^(M-1) + s[i+1]·B^(M-2) + ... + s[i+M-1]·B^0) mod MOD

B 는 진법 (보통 31, 37, 256 등), MOD 는 큰 소수 (1e9+7, 1e9+9, 2^61-1).

롤링 갱신 (i → i+1 슬라이딩):

H(s[i+1..i+M]) = (H(s[i..i+M-1]) - s[i]·B^(M-1)) · B + s[i+M]   (mod MOD)

O(1) 에 다음 윈도우 해시 계산. 패턴 해시 H(P) 와 비교 → 일치 시 실제 비교 (해시 충돌 검증).

amortized O(N + M): N 개 윈도우 해시 각 O(1), 충돌 거의 없으면 실제 비교 O(M) 이 상수 번.

알고리즘

rabin_karp(T[0..N-1], P[0..M-1]):
    hP = hash(P)
    hT = hash(T[0..M-1])
    power = B^(M-1) mod MOD

    for i = 0..N-M:
        if hT == hP:
            if T[i..i+M-1] == P:
                report match at i
        if i < N - M:
            hT = ((hT - T[i] * power) * B + T[i+M]) mod MOD

구현

// 라빈-카프 패턴 매칭, 평균 O(N + M)
#include <bits/stdc++.h>
using namespace std;
const long long B = 31, MOD = 1e9 + 7;
​
long long hash_str(const string& s) {
  long long h = 0;
  for (char c : s) h = (h * B + (c - 'a' + 1)) % MOD;
  return h;
}
​
vector<int> rabin_karp(const string& T, const string& P) {
  int N = T.size(), M = P.size();
  if (M > N) return {};
  long long hP = hash_str(P), hT = hash_str(T.substr(0, M));
  long long power = 1;
  for (int i = 0; i < M - 1; i++) power = (power * B) % MOD;
​
  vector<int> matches;
  for (int i = 0; i <= N - M; i++) {
      if (hT == hP && T.substr(i, M) == P) matches.push_back(i);
      if (i < N - M) {
          hT = ((hT - (T[i] - 'a' + 1) * power % MOD + MOD) % MOD * B 
                + (T[i + M] - 'a' + 1)) % MOD;
      }
  }
  return matches;
}
​
int main() {
  string T, P;
  cin >> T >> P;
  auto res = rabin_karp(T, P);
  cout << res.size() << "\n";
  for (int pos : res) cout << pos << " ";
  if (!res.empty()) cout << "\n";
}

# 라빈-카프 O(N + M) 평균
B, MOD = 31, 10**9 + 7
​
def hash_str(s):
  h = 0
  for c in s:
      h = (h * B + ord(c) - ord('a') + 1) % MOD
  return h
​
def rabin_karp(T, P):
  N, M = len(T), len(P)
  if M > N:
      return []
  hP = hash_str(P)
  hT = hash_str(T[:M])
  power = pow(B, M - 1, MOD)
  matches = []
  for i in range(N - M + 1):
      if hT == hP and T[i:i+M] == P:
          matches.append(i)
      if i < N - M:
          hT = ((hT - (ord(T[i]) - ord('a') + 1) * power) * B 
                + (ord(T[i+M]) - ord('a') + 1)) % MOD
  return matches
​
T = input().strip()
P = input().strip()
res = rabin_karp(T, P)
print(len(res))
if res:
  print(*res)

// 라빈-카프 O(N + M) 평균
import java.util.*;
public class Main {
  static final long B = 31, MOD = 1_000_000_007;
  static long hashStr(String s) {
      long h = 0;
      for (char c : s.toCharArray())
          h = (h * B + (c - 'a' + 1)) % MOD;
      return h;
  }
  static List<Integer> rabinKarp(String T, String P) {
      int N = T.length(), M = P.length();
      if (M > N) return new ArrayList<>();
      long hP = hashStr(P), hT = hashStr(T.substring(0, M));
      long power = 1;
      for (int i = 0; i < M - 1; i++) power = (power * B) % MOD;
      List<Integer> matches = new ArrayList<>();
      for (int i = 0; i <= N - M; i++) {
          if (hT == hP && T.substring(i, i + M).equals(P))
              matches.add(i);
          if (i < N - M) {
              hT = ((hT - (T.charAt(i) - 'a' + 1) * power % MOD + MOD) % MOD * B
                    + (T.charAt(i + M) - 'a' + 1)) % MOD;
          }
      }
      return matches;
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String T = sc.next(), P = sc.next();
      List<Integer> res = rabinKarp(T, P);
      System.out.println(res.size());
      for (int pos : res) System.out.print(pos + " ");
      if (!res.isEmpty()) System.out.println();
  }
}

ababcababc
abc

2
2 7

aaaaaaa
aa

6
0 1 2 3 4 5

복잡도

최악 케이스는 모든 윈도우 해시가 패턴 해시와 같지만 실제 문자열은 다를 때. 하지만 좋은 MOD (큰 소수) 와 B 선택 시 충돌 확률 < 1/MOD.

변형 / 활용

1. 다중 패턴 매칭

패턴 K 개 P_1, ..., P_K 를 모두 찾기. 패턴 해시 K 개를 set 에 저장 → 텍스트 해시 O(N) 스캔 → set 조회 O(log K) → 총 O(N log K + Σ M_i).

2. 2D 패턴 매칭

이미지 (2D 배열) 에서 템플릿 찾기. 각 행을 해시 → 열 방향 롤링 해시. O(HW) (H, W 는 텍스트 크기).

3. double hashing

충돌 확률 줄이기 위해 두 modulo (MOD1, MOD2) 동시 사용. 둘 다 일치 시 실제 비교. 충돌 확률 < 1/(MOD1 · MOD2).

함정

1. 음수 해시

hT - (T[i] - 'a' + 1) * power 가 음수 될 수 있다. + MOD 후 다시 mod 필요.

hT = ((hT - val * power % MOD + MOD) % MOD * B + next) % MOD;

2. 해시 충돌

작은 MOD (예: 1e6+3) 는 충돌 많음. 1e9+7, 1e9+9, 2^61-1 같은 큰 소수 사용.

3. B 선택

B=26 은 알파벳만 구별 → 충돌 많음. B=31, 37 추천. 대소문자 구별 시 B=256.

4. overflow

power * B 계산 시 long long overflow. (power * B) % MOD 반드시.

BOJ 연습 문제

참고

• KMP
• Z 알고리즘
• Hashing