[알고리즘] 롤링 해시 - 라빈 카프 알고리즘 (Rabin-Karp)

이상현·2025년 3월 11일

알고리즘

목록 보기

11/15

문자열에서 부분 문자열 찾기

"aaaaaaaaaaab" 안에 "aaaab" 가 존재하는지 찾아보자.

일반적인 방법 (브루트포스) 이라면, 우선 첫 번째 요소부터 시작해서 5개를 추출하고, 또 다시 그 다섯개와 목표 문자열을 하나하나 비교할 것이다.

이렇게 마지막까지 반복하고 최종적으로 $O(N * M)$ 의 시간복잡도를 가진다.
(문자열의 길이: $N$ , 부분문자열의 길이: $M$ )

라빈 카프는 이 작업을 $O(N)$ 에 할수 있게 해준다.

라빈 카프

라빈 카프의 개념은 슬라이딩 윈도우 / 투포인터 와 비슷하다. 전체를 계산하는 것이 아니라 움직일때 마다 값을 하나 추가하거나 뺀다.

라빈 카프의 특징

문자열 해시 알고리즘이다. 문자열에 특정 계산을 해서 숫자 하나로 특정한다.
특정 문자열의 해시에서 문자 하나를 추가하거나 뺀 해시 값을 계산할 수 있다.
위 두가지 특성 덕분에 부분 문자열을 자주 비교해야 하는 경우에 매우 효율적으로 동작한다.

라빈 카프 일반화

$H = (∑_{i=0}^{l-1} C_i * r^{l-1-i} ) \mod m$

( $H$ : 해시 값, $C_i$ : 문자열의 i 번째 문자, $r$ : 해싱의 기준이 되는 소수, $m$ : 해시 값을 나누는 큰 소수, $l$ : C문자의 길이)

식은 복잡하니 예시로 이해해 보자.

라빈 카프 알고리즘과 롤링 해시

( $r=10$ , $m=113$ 일 때)
"abcd" 라는 문자열의 해시를 라빈 카프 알고리즘으로 구하면 다음과 같은 값이 나온다.

$h(abcd)$
$= h(1,2,3,4)$
$= (1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 * 10^0) \mod 113$
$= 104$

다음으로, "bcde" 의 해시 값을 롤링 해시를 사용해서 구해보자.
1. "abcd" 의 해시값에서 "a"에 해당 하는 해시 값을 빼고
2. 전체에 10을 곱하고
3. "e"에 대한 해시값을 더하면 된다.
4. 중간 중간에 mod 연산을 해줘야 음수가 되지 않는다.

$h(bcde)$
$= (((h(abcd) - 1 * 10^3 \mod 113) * 10) \mod 113 + 5 * 10^0) \mod 113$
$= (((104 - 96) * 10) \mod 113 + 5) \mod 113$
$= (80 \mod 113 + 5) \mod 113$
$= 85$

확인 해보면 $h(bcde) = h(2,3,4,5) = 2345 \mod 113 = 85$ 로 맞다.

위와 같은 연산을 작용하면, 부분 문자열이 아무리 길어도 $O(1)$ 의 계산으로 다음 부분문자열의 해시값을 알 수 있다.

해시 충돌 방지

위에 예시에서는 $r$ 과 $m$ 에 임의로 $10$ 과 $113$ 이라는 숫자를 사용했다.
$r$ 과 $m$ 는 아무 값이나 가능하지만, 큰 소수를 사용해야 해시 충돌 확률이 작다.

$r$ 은 사용할 문자의 개수 (소문자 영어는 26개) 이상으로 잡으므로, 31 또는 53 등을 사용한다.
$m$ 은 큰 소수이면서 외우기 쉬운 1,000,000,007 (10억 7) 또는 1,234,567,891 같은 수를 사용한다.
(매우 큰 수로는 10^14+31 = 100,000,000,000,031 이 있다.)

문제 풀이

백준 3033 - 부분 문자열 찾기, 라빈 카프 알고리즘 연습문제

위 문제는 lcp 알고리즘 또는 이분 탐색 + 라빈 카프 알고리즘으로 풀린다.

자바의 구현체인 HashMap 으로는 문자열의 최대 길이가 200,000 이므로 모든 부분 문자열을 저장해 버리면 메모리 초과가 난다. 그래서 해싱으로 풀려면 필수적으로 해싱 알고리즘을 구현해야하는 문제이다.

라빈-카프 알고리즘으로 풀 경우 $M$ 값을 매우 크게 잡지 않으면 해싱 충돌이 일어나 실패가 뜨니까 주의하자.

이 문제에 파라매트릭 서치 (이분 탐색)를 사용한다.

import java.util.*;
import java.io.*;

public class Main {
    private static final long MOD = 100_000_000_000_031L;
    private static final int X = 31;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int l = Integer.parseInt(br.readLine());
        String str = br.readLine();
        int start = 1;
        int end = l - 1;

        int ans = 0;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (isValid(str, mid)) {
                ans = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        System.out.println(ans);
    }

    private static boolean isValid(String str, int x) {
        Set<Long> set = new HashSet<>();
        long hash = 0;
        long X_power = 1;

        for (int i = 0; i < x; i++) {
            hash = (hash * X + str.charAt(i)) % MOD;
            if (i > 0) {
                X_power = (X_power * X) % MOD;
            }
        }
        set.add(hash);

		// 매번 해시값을 계산하는게 아니라, 필요한 값만 뺴고 더하면서 구한다.
        for (int i = x; i < str.length(); i++) {
            hash = (hash - (str.charAt(i - x) * X_power) % MOD + MOD) % MOD;
            hash = (hash * X + str.charAt(i)) % MOD;
            if (set.contains(hash)) {
                return true;
            }

            set.add(hash);
        }
        return false;
    }
}