라빈-카프

패턴과 텍스트의 부분 문자열을 직접 비교하는 대신 해시값으로 비교하고, 한 글자씩 이동할 때마다 해시를 처음부터 다시 계산하지 않고 롤링 해시로 O(1)에 갱신해 문자열을 찾는 알고리즘입니다.

동작 과정

준비: 문자를 숫자로, 해시 함수 정의

설명을 단순하게 하기 위해 A=1, B=2, C=3으로 두고, 밑수(d)=10, 소수(q)=13인 해시를 사용합니다.

text    = "ABABABABC"   (digits: 1 2 1 2 1 2 1 2 3)
pattern = "ABABC"       (digits: 1 2 1 2 3)
m = 5, n = 9, d = 10, q = 13

h = d^(m-1) mod q = 10^4 mod 13 = 3        (윈도우 한 칸 이동 시 선두 자리를 지우는 데 쓰임)
patternHash = 12123 mod 13 = 7

1단계: 첫 윈도우 해시 계산 후 비교

window0 = text[0..4] = "ABABA" = 12121 → mod 13 = 5
patternHash(7) != windowHash(5)  → 문자 비교 없이 바로 건너뜀

2단계: 롤링 해시로 한 칸씩 이동

매번 전체를 다시 계산하지 않고 아래 점화식으로 갱신합니다.

windowHash(i+1) = ( d * ( windowHash(i) - text[i] * h ) + text[i+m] ) mod q

window1 = (10*(5 - 1*3) + 2) mod 13 = 9   → "BABAB"=21212 mod13=9 (검증됨), patternHash(7)!=9 → 건너뜀
window2 = (10*(9 - 2*3) + 1) mod 13 = 5   → "ABABA" 와 동일한 자리수라 5, 7!=5 → 건너뜀
window3 = (10*(5 - 1*3) + 2) mod 13 = 9   → "BABAB" 패턴과 같아 9, 7!=9 → 건너뜀
window4 = (10*(9 - 2*3) + 3) mod 13 = 7   → patternHash(7) == windowHash(7) → 해시 일치!

3단계: 해시가 일치하면 실제 문자열로 검증

window4 = text[4..8] = "ABABC"
pattern  = "ABABC"
문자 하나씩 비교 → 전부 일치 → index 4 에서 매칭 확정

해시가 같다고 바로 매칭으로 확정하면 안 됩니다. 서로 다른 문자열이 같은 해시값으로 충돌할 수 있기 때문에(해시 충돌), 해시가 일치한 구간만 실제 문자 비교로 한 번 더 검증합니다.

구현

List<Integer> rabinKarp(String text, String pattern) {
    List<Integer> result = new ArrayList<>();
    int n = text.length();
    int m = pattern.length();
    if (m == 0 || m > n) return result;

    long d = 256;              // 문자 집합 크기(바이트 기준 밑수)
    long q = 1_000_000_007L;   // 해시 충돌 확률을 낮추는 큰 소수

    long h = 1;                // d^(m-1) mod q
    for (int i = 0; i < m - 1; i++) {
        h = (h * d) % q;
    }

    long patternHash = 0;
    long windowHash = 0;
    for (int i = 0; i < m; i++) {
        patternHash = (patternHash * d + pattern.charAt(i)) % q;
        windowHash = (windowHash * d + text.charAt(i)) % q;
    }

    for (int i = 0; i <= n - m; i++) {
        if (patternHash == windowHash && text.substring(i, i + m).equals(pattern)) {
            result.add(i);
        }
        if (i < n - m) {
            long removed = (text.charAt(i) * h) % q;
            windowHash = (windowHash - removed + q) % q;
            windowHash = (windowHash * d + text.charAt(i + m)) % q;
        }
    }
    return result;
}

복잡도

구분복잡도근거
전처리O(M)패턴 해시와 d^(m-1) mod q 계산
검색 (평균)O(N)각 윈도우 해시 갱신이 O(1), 해시가 일치할 때만 O(M) 검증 발생
검색 (최악)O(NM)해시 충돌이 계속 겹쳐 매 윈도우마다 검증이 발생하는 경우
공간O(1)해시값 몇 개만 유지(결과 리스트 제외)

q를 충분히 큰 소수로 두면 충돌 확률이 낮아져 평균적으로 O(N+M)에 가깝게 동작하지만, 이론적 최악의 경우는 여전히 O(NM)입니다. KMP는 입력과 무관하게 항상 O(N+M)을 보장한다는 점이 다릅니다.

주의사항

핵심 정리

CSLOG에서 보기