문자열 해싱 (String Hashing)

정의

문자열 해싱 (String Hashing) 은 문자열을 고정 길이의 정수 (해시값) 로 매핑하여, 부분 문자열 비교를 O(1) 에 수행할 수 있게 만드는 기법. Rabin과 Karp가 1987년에 제안한 Rabin-Karp 알고리즘 이 대표적.

핵심은 rolling hash, polynomial hash, 그리고 충돌 가능성 관리.

문제 상황과 동기

길이 N 문자열 S 에서 길이 M 패턴 P 를 찾거나, Q 개 부분 문자열 쌍의 일치 여부를 묻는다.

• naive 비교: 매 쿼리 O(M), 총 O(N · M) 또는 O(M · Q). N=10^5, M=10^5 면 10^10, 불가.
• 해시 기반: O(N) 전처리 + O(1) 비교. 총 O(N + Q).

핵심 통찰: 문자열을 다항식 계수로 보고 mod p 에서 값을 계산하면, 누적 합 처럼 구간 해시를 O(1) 에 추출 가능.

충돌 확률은 생일 역설 수준, 하지만 실무/대회는 해시가 10배 빠르므로 확률적으로 허용.

시각화

핵심 아이디어

문자열 s[0..N-1] 을 base-B 다항식 으로 간주:

H(s[0..k]) = s[0]·B^k + s[1]·B^(k-1) + ... + s[k]·B^0  (mod P)

• B (base): 보통 31, 37, 53 같은 소수 또는 1e9+7 근처 큰 소수. 문자 집합 크기보다 큰 값.
• P (modulus): 큰 소수 (10^9+7, 10^9+9) 또는 2^61-1. overflow 방지 + 충돌률 감소.

rolling hash 는 H(s[0..k]) 를 알 때 H(s[0..k+1]) 을 O(1) 갱신:

H(s[0..k+1]) = (H(s[0..k]) · B + s[k+1]) mod P

부분 문자열 해시 H(s[l..r]) 는:

H(s[l..r]) = (H(s[0..r]) - H(s[0..l-1]) · B^(r-l+1)) mod P

prefix hash 와 power 배열 pow[i] = B^i mod P 를 전처리하면 O(1).

알고리즘

build_hash(s):
    N = len(s)
    H[0] = 0
    pow[0] = 1
    for i = 1..N:
        H[i] = (H[i-1] · B + s[i-1]) mod P
        pow[i] = (pow[i-1] · B) mod P

hash(l, r):  # 0-indexed, inclusive
    return (H[r+1] - H[l] · pow[r-l+1] + P·P) mod P

주의: 음수 mod 처리 + P·P 또는 ((...) % P + P) % P.

구현

// Rolling hash with base B=31, mod P=1e9+7
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, B = 31;
int main() {
  string s; cin >> s;
  int n = s.size(), q; cin >> q;
  vector<long long> H(n + 1), pw(n + 1);
  H[0] = 0; pw[0] = 1;
  for (int i = 1; i <= n; i++) {
      H[i] = (H[i-1] * B + (s[i-1] - 'a' + 1)) % P;
      pw[i] = (pw[i-1] * B) % P;
  }
  auto hash = [&](int l, int r) {
      return ((H[r+1] - H[l] * pw[r-l+1]) % P + P) % P;
  };
  while (q--) {
      int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
      cout << (hash(l1, r1) == hash(l2, r2) ? "YES" : "NO") << "\n";
  }
}

# Python rolling hash (주의: 느림, PyPy 권장)
import sys
input = sys.stdin.readline
P, B = 10**9 + 7, 31
​
s = input().strip()
n = len(s)
q = int(input())
H = [0] * (n + 1)
pw = [1] * (n + 1)
​
for i in range(1, n + 1):
  H[i] = (H[i-1] * B + (ord(s[i-1]) - ord('a') + 1)) % P
  pw[i] = (pw[i-1] * B) % P
​
def hash_range(l, r):
  return (H[r+1] - H[l] * pw[r-l+1]) % P
​
out = []
for _ in range(q):
  l1, r1, l2, r2 = map(int, input().split())
  out.append("YES" if hash_range(l1, r1) == hash_range(l2, r2) else "NO")
print("\n".join(out))

// Java rolling hash, 1-indexed query
import java.util.*;
import java.io.*;
public class Main {
  static final long P = 1_000_000_007L, B = 31L;
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String s = br.readLine();
      int n = s.length(), q = Integer.parseInt(br.readLine());
      long[] H = new long[n + 1], pw = new long[n + 1];
      pw[0] = 1;
      for (int i = 1; i <= n; i++) {
          H[i] = (H[i-1] * B + (s.charAt(i-1) - 'a' + 1)) % P;
          pw[i] = (pw[i-1] * B) % P;
      }
      StringBuilder sb = new StringBuilder();
      while (q-- > 0) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int l1 = Integer.parseInt(st.nextToken());
          int r1 = Integer.parseInt(st.nextToken());
          int l2 = Integer.parseInt(st.nextToken());
          int r2 = Integer.parseInt(st.nextToken());
          long h1 = ((H[r1+1] - H[l1] * pw[r1-l1+1]) % P + P) % P;
          long h2 = ((H[r2+1] - H[l2] * pw[r2-l2+1]) % P + P) % P;
          sb.append(h1 == h2 ? "YES" : "NO").append('\n');
      }
      System.out.print(sb);
  }
}

abcabc
3
0 2 3 5
0 1 1 2
0 0 3 3

YES
NO
YES

복잡도

충돌 가능성

해시는 확률적 알고리즘. 서로 다른 문자열이 같은 해시값을 가질 확률은:

Pr[collision] ≈ 1/P

Q개 쿼리, P=10^9+7 이면 Q ≤ 10^5 까지는 충돌 확률 ~10^-4. 실무에선 double hashing (두 개의 (B, P) 쌍) 사용:

hash1 = (H1[r+1] - H1[l] * pw1[r-l+1]) % P1;
hash2 = (H2[r+1] - H2[l] * pw2[r-l+1]) % P2;
if (hash1 == hash1' && hash2 == hash2') ...

충돌 확률 ~1/(P1·P2) 로 사실상 0.

변형 / 활용

1. Rabin-Karp 패턴 매칭

길이 M 패턴 P 의 해시를 계산, S 의 모든 길이-M 구간 해시와 비교. O(N+M).

2. 회문 판정

H(s[l..r]) 와 H_rev(s[N-r-1..N-l-1]) 비교. 역방향 해시 배열 추가.

3. 최장 공통 접두사 (LCP)

이진 탐색 + 해시. mid 길이까지 해시 일치하는지 확인. O(log N) per query.

4. 부분 문자열 중복 제거

모든 부분 문자열의 해시를 set 에 넣어 unique count. O(N^2).

함정

1. 음수 mod

(H[r] - H[l] * pw[len]) % P 가 음수. C++ 에서 % P 는 [-P+1, P-1] 범위. + P 후 다시 mod 또는 ((... % P) + P) % P.

2. overflow

H[i] * B 또는 pw[i] 계산 시 long long 범위 초과 가능. (__int128) 또는 modular 곱셈 ((a * b) % P 를 mulmod 로).

3. base 선택

B가 너무 작으면 (B=26) 충돌 증가. B가 너무 크면 (B=1e9) overflow. 보통 31~53 소수가 안전.

4. 충돌 공격

해커가 의도적으로 충돌 유발 가능 (예: B, P를 알 때). 보안 필요 시 랜덤 B 사용 또는 double hashing.

5. 0번 문자 처리

s[i] - 'a' 가 0일 때 leading zero 문제. 보통 s[i] - 'a' + 1 로 1-indexed 매핑.

BOJ 연습 문제

참고

• KMP 알고리즘 (해시 없이 패턴 매칭, O(N+M) 확정)
• Z 알고리즘 (prefix 일치 길이, O(N) 확정)
• 트라이 (여러 패턴 동시 처리)
• 접미사 배열 (모든 부분 문자열 정렬)