문자열 해싱(String Hashing)은 문자열에 다항식 해시 함수를 적용해 부분 문자열 비교를 O(1)에 수행하는 기법이다. 라빈-카프 알고리즘의 핵심이며 문자열 관련 경쟁 프로그래밍에서 광범위하게 사용된다.
핵심 원리
hash(s) = s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1] (mod m)
접두사 해시 배열을 전처리하면 임의 부분 문자열의 해시를 O(1) 계산 가능:
hash(s[l..r]) = (h[r+1] - h[l] * p^(r-l+1)) mod m
구현
python
class StringHash:
def __init__(self, s, base=131, mod=10**18+9):
n = len(s)
self.mod = mod
self.base = base
self.h = [0] * (n + 1)
self.pw = [1] * (n + 1)
for i in range(n):
self.h[i+1] = (self.h[i] * base + ord(s[i])) % mod
self.pw[i+1] = self.pw[i] * base % mod
def get(self, l, r): # [l, r] 0-indexed
return (self.h[r+1] - self.h[l] * self.pw[r-l+1]) % self.mod
def longest_common_prefix(s, t):
"""이분 탐색 + 해싱으로 LCP 계산"""
hs = StringHash(s)
ht = StringHash(t)
lo, hi = 0, min(len(s), len(t))
while lo < hi:
mid = (lo + hi + 1) // 2
if hs.get(0, mid-1) == ht.get(0, mid-1):
lo = mid
else:
hi = mid - 1
return lo
해시 충돌 방지
- •이중 해싱: 두 개의 다른 모듈러 값 사용
- •큰 소수 mod 사용 (10^9+7, 10^18+9)
관련 개념
