Algorithm // Rolling Hash

Alpha, Orderly·2026년 6월 29일

코딩 알고리즘

목록 보기

7/9

문자열의 비교

보통 두 문자열의 동일성 유무 비교는 O(N) 시간복잡도가 들기 마련이다.

def comparator(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    for i in range(len(a)):
        if a[i] != b[i]:
            return False
    return True

만약 문자열을 적절히 해싱할수 있다면 정수와 정수간의 비교로 변환해 O(1)이 될 것이다.

롤링 해시

롤링해시의 값의 표현은 다음과 같다.

Ex. 문자열 "ABCD"에 대해 각 A, B, C, D 는 ascii 숫자로 변환했다고 가정한다. 또한 X는 임의 크기의 적당한 소수이다.

A \times X^3 + B \times X^2 + C \times X^1 + D \times X^0

이렇게 나온 값을 비교하면 곧 문자열의 비교가 가능해지는것이다!

어떤게 좋을까?

근데 만약 다른 문자열에 대해 롤링 해시를 하나하나 다 계산해야 한다면, 어차피 계산 과정에서 시간복잡도가 O(N)이 소요되기에 의미가 없을것이다.
하지만 롤링해시의 진짜 장점은 따로 있다!

문자열의 앞뒤에 문자를 한개 빼거나 추가하는 과정이 O(1)에 일어난다.

즉, 문자열 전체를 처음부터 다시 계산하는게 아니라, 기존의 해시값을 이용해 다음 해시값을 빠르게 계산할수 있다는 점이 핵심이다.

예를 들어 문자열 "ABCD"의 해시값이 다음과 같다고 해보자.

A \times X^3 + B \times X^2 + C \times X^1 + D \times X^0

여기서 맨 앞의 A를 제거하고, 뒤에 E를 추가해서 "BCDE"의 해시값을 만들고 싶다면?

원래대로라면 "BCDE"에 대해 다시

B \times X^3 + C \times X^2 + D \times X^1 + E \times X^0

를 처음부터 계산해야 한다.

하지만 기존 해시값을 잘 이용하면 이렇게 계산할수 있다.

기존 해시값에서 A * X^3을 제거한다.
남은 값을 X배 해서 자리수를 하나 올린다.
마지막에 E를 더한다.

즉,

hash(ABCD) - A \times X^3

를 한 뒤,

(hash(ABCD) - A \times X^3) \times X + E

를 하면 "BCDE"의 해시값이 된다.

이 과정은 문자열 길이와 상관없이 O(1)에 수행된다.
그래서 슬라이딩 윈도우처럼 문자열의 일정 구간을 계속 이동하며 비교해야 하는 상황에서 롤링 해시가 강력하다.

예시

문자열 "ABCDE"에서 길이 3짜리 부분 문자열을 비교한다고 해보자.

부분 문자열은 다음과 같다.

ABC
BCD
CDE

각 문자열을 매번 직접 비교하거나 해시를 새로 계산하면, 길이 3만큼의 시간이 계속 든다.

하지만 롤링 해시를 사용하면

hash(ABC) -> hash(BCD) -> hash(CDE)

처럼 이전 해시값을 이용해 다음 해시값을 O(1)에 얻을수 있다.

MOD 연산

다만 실제로는 해시값을 그대로 저장하지 않는 경우가 많다.
문자열이 길어질수록 값이 너무 커지기 때문이다.

예를 들어 "ABCD"의 해시값은

A \times X^3 + B \times X^2 + C \times X^1 + D \times X^0

정도지만, 문자열의 길이가 수십만이 된다면 X의 거듭제곱 값이 말도 안되게 커질 것이다.

그래서 보통은 MOD 연산을 같이 사용한다.

MOD = 10 ** 9 + 7
BASE = 31

그리고 해시값을 계산할때마다 다음처럼 MOD를 취해준다.

hash_value %= MOD

즉, 실제로는 다음과 같은 형태로 계산한다.

hash(S) = (S_0 \times X^{N-1} + S_1 \times X^{N-2} + ... + S_{N-1} \times X^0) \mod MOD

이렇게 하면 값이 너무 커지는 것을 막을수 있다.

주의할 점

다만 해시값이 같다고 해서 두 문자열이 반드시 같다고 볼수는 없다.
서로 다른 문자열인데 우연히 같은 해시값이 나올수 있기 때문이다.

이를 해시 충돌이라고 한다.

예를 들어 두 문자열이 서로 다르더라도, MOD 연산을 거친 결과가 같을수 있다.

hash(A) == hash(B)

라고 해서 반드시

A == B

라고 보장할수는 없는 것이다.

그래서 롤링 해시는 보통 다음과 같은 방식으로 사용한다.

충돌 가능성이 매우 낮다고 보고 사용한다.
MOD를 2개 사용해서 충돌 가능성을 더 낮춘다.
해시값이 같은 경우 실제 문자열을 한번 더 비교한다.

코딩테스트에서는 보통 적절한 BASE, MOD를 사용하면 충돌 가능성이 매우 낮기 때문에 해시값 비교만으로 처리하는 경우도 많다.

구현 예시

길이 k짜리 부분 문자열의 해시값을 롤링하면서 계산하는 예시는 다음과 같다.

def rolling_hash(s: str, k: int):
    MOD = 10 ** 9 + 7
    BASE = 31

    def to_int(ch: str) -> int:
        return ord(ch) - ord('a') + 1

    n = len(s)

    if n < k:
        return []

    hash_value = 0

    for i in range(k):
        hash_value = (hash_value * BASE + to_int(s[i])) % MOD

    result = [hash_value]

    power = pow(BASE, k - 1, MOD)

    for i in range(k, n):
        left = to_int(s[i - k])
        right = to_int(s[i])

        hash_value = (hash_value - left * power) % MOD
        hash_value = (hash_value * BASE + right) % MOD

        result.append(hash_value)

    return result

예를 들어

rolling_hash("abcde", 3)

를 수행하면 내부적으로는 다음과 같이 진행된다.

abc
bcd
cde

처음 abc의 해시값은 직접 계산한다.

그 다음 bcd의 해시값은 abc의 해시값에서 a를 제거하고, d를 추가해서 계산한다.

그 다음 cde의 해시값은 bcd의 해시값에서 b를 제거하고, e를 추가해서 계산한다.

즉, 매번 길이 3만큼 다시 계산하는게 아니라, 이전 해시값을 이용해 다음 해시값을 빠르게 만드는 것이다.

정리

롤링 해시의 사용 이유는 다음과 같이 볼수 있다.

문자열을 숫자로 변환해서 빠르게 비교할수 있다.
문자열의 앞뒤에 문자를 추가하거나 제거했을때, 다음 해시값을 O(1)에 계산할수 있다.
그래서 긴 문자열에서 여러 부분 문자열을 비교할때 유용하다.

즉, 단순히 문자열 하나를 해싱하는 것만으로는 큰 의미가 없다.

진짜 핵심은

이전 해시값을 이용해 다음 문자열의 해시값을 빠르게 계산할수 있다.

는 점이다.

사용 예시

패턴 매칭

롤링 해시를 이용하면 긴 문자열 안에서 특정 패턴이 등장하는지도 빠르게 확인할수 있다.

예를 들어 긴 문자열 text 안에서 pattern이 존재하는지 찾는다고 해보자.

일반적인 방식이라면 text의 각 위치마다 pattern과 직접 비교해야 한다.

def find_pattern(text: str, pattern: str) -> bool:
    n = len(text)
    m = len(pattern)

    for i in range(n - m + 1):
        if text[i:i + m] == pattern:
            return True

    return False

이 방식은 최악의 경우 각 위치마다 길이 m만큼 비교해야 하므로 시간복잡도는 O(NM)이 될수 있다.

하지만 롤링 해시를 사용하면 다음과 같이 생각할수 있다.

먼저 pattern의 해시값을 구한다.
text에서 길이가 len(pattern)인 부분 문자열들의 해시값을 구한다.
두 해시값이 같은 위치를 찾는다.

즉,

text    = "ababcabc"
pattern = "abc"

라면 text에서 길이 3짜리 부분 문자열들을 확인한다.

aba
bab
abc
bca
cab
abc

이때 각 부분 문자열의 해시값을 매번 새로 계산하지 않고, 롤링 해시로 이전 해시값을 이용해 다음 해시값을 O(1)에 계산한다.

패턴 매칭 구현 예시

def rabin_karp(text: str, pattern: str) -> list[int]:
    MOD = 10 ** 9 + 7
    BASE = 31

    def to_int(ch: str) -> int:
        return ord(ch) - ord('a') + 1

    n = len(text)
    m = len(pattern)

    if n < m:
        return []

    pattern_hash = 0
    window_hash = 0

    for i in range(m):
        pattern_hash = (pattern_hash * BASE + to_int(pattern[i])) % MOD
        window_hash = (window_hash * BASE + to_int(text[i])) % MOD

    result = []

    if pattern_hash == window_hash:
        result.append(0)

    power = pow(BASE, m - 1, MOD)

    for i in range(m, n):
        left = to_int(text[i - m])
        right = to_int(text[i])

        window_hash = (window_hash - left * power) % MOD
        window_hash = (window_hash * BASE + right) % MOD

        if window_hash == pattern_hash:
            result.append(i - m + 1)

    return result

사용 예시는 다음과 같다.

text = "ababcabc"
pattern = "abc"

print(rabin_karp(text, pattern))

결과는 다음과 같다.

[2, 5]

즉, "abc"는 text의 2번 인덱스와 5번 인덱스에서 등장한다.

실제 문자열 비교를 추가한 버전

다만 앞에서 말했듯이 해시 충돌이 발생할수 있다.

그래서 안전하게 구현하려면 해시값이 같은 경우 실제 문자열도 한번 더 비교해주는 방식이 좋다.

def rabin_karp_safe(text: str, pattern: str) -> list[int]:
    MOD = 10 ** 9 + 7
    BASE = 31

    def to_int(ch: str) -> int:
        return ord(ch) - ord('a') + 1

    n = len(text)
    m = len(pattern)

    if n < m:
        return []

    pattern_hash = 0
    window_hash = 0

    for i in range(m):
        pattern_hash = (pattern_hash * BASE + to_int(pattern[i])) % MOD
        window_hash = (window_hash * BASE + to_int(text[i])) % MOD

    result = []

    if pattern_hash == window_hash and text[0:m] == pattern:
        result.append(0)

    power = pow(BASE, m - 1, MOD)

    for i in range(m, n):
        left = to_int(text[i - m])
        right = to_int(text[i])

        window_hash = (window_hash - left * power) % MOD
        window_hash = (window_hash * BASE + right) % MOD

        start = i - m + 1

        if window_hash == pattern_hash and text[start:start + m] == pattern:
            result.append(start)

    return result

이렇게 하면 해시값이 같은 경우에만 실제 문자열 비교를 수행한다.

즉, 대부분의 경우에는 O(1) 해시 비교만 수행하고, 해시값이 같은 경우에만 추가 비교를 하게 된다.

시간복잡도

패턴의 길이를 M, 전체 문자열의 길이를 N이라고 하면

pattern의 해시값 계산: O(M)
text의 첫 윈도우 해시값 계산: O(M)
이후 윈도우 이동: O(N - M)
각 위치에서 해시 비교: O(1)

따라서 평균적으로 O(N + M)에 패턴 매칭을 수행할수 있다.

물론 해시 충돌이 많이 발생해서 매번 실제 문자열 비교가 일어나면 최악의 경우 O(NM)이 될수 있다.

하지만 적절한 BASE, MOD를 사용하면 실제로는 충돌 가능성이 매우 낮기 때문에 빠르게 동작한다.

정리하면

롤링 해시를 이용한 패턴 매칭은 다음과 같은 흐름이다.

찾고 싶은 문자열인 pattern의 해시값을 구한다.
text에서 pattern과 같은 길이의 구간 해시값을 구한다.
구간을 한칸씩 이동하며 해시값을 O(1)에 갱신한다.
pattern_hash == window_hash인 위치를 찾는다.
충돌이 걱정된다면 실제 문자열 비교를 한번 더 한다.

즉, 롤링 해시를 이용하면 긴 문자열 안에서 특정 문자열을 찾는 작업을 매우 빠르게 처리할수 있다.

Alpha, Orderly

만능 컴덕후 겸 번지 팬

이전 포스트

Algorithm // Lowest Common Ancestor ( LCA )

다음 포스트