꿀팁: 결정론적 문자열 알고리즘을 모두 익히기 전까지는 해시를 사용하는 법을 익히십시오.
문자열은 $1$부터 $m$(알파벳 크기)까지의 수로 이루어진 수열이라고 가정하겠습니다. C/C++에서 char 타입은 사실 (8비트) 수이기도 하므로, 문자에서 최소 코드를 빼고 수로 캐스팅할 수 있습니다:
int x = (int) (c - 'a' + 1);
문자열의 직접 다항식 해시를 다음 다항식의 값으로 정의합시다:
$$ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + s_n k^n) \bmod p $$여기서 $k$는 알파벳 크기보다 큰 임의의 수이고, $p$는 충분히 큰 모듈러(일반적으로 반드시 소수일 필요는 없음)입니다.
이는 $k$의 필요한 거듭제곱 값을 담는 변수를 유지하면서 선형 시간에 계산할 수 있습니다:
const int k = 31, mod = 1e9+7;
string s = "abacabadaba";
long long h = 0, m = 1;
for (char c : s) {
int x = (int) (c - 'a' + 1);
h = (h + m * x) % mod;
m = (m * k) % mod;
}
역다항식 해시도 정의할 수 있습니다:
$$ h_b = (s_0 k^n + s_1 k^{n-1} + \ldots + s_n) \mod p $$이 해시의 장점은 코드를 한 줄 덜 작성해도 된다는 점입니다:
long long h = 0;
for (char c : s) {
int x = (int) (c - 'a' + 1);
h = (h * k + x) % mod;
}
저자는 일반적인 다항식으로 생각하는 편이 더 쉽기 때문에, 앞으로 모든 곳에서 정방향 다항식 해시를 사용하고 이를 간단히 문자 $h$로 표기하겠습니다.
#이것이 왜 필요합니까?
해시가 다항식의 값이라는 사실을 이용하면, 여러 문자열 연산을 수행한 결과의 해시를 빠르게 다시 계산할 수 있습니다.
예를 들어, 문자열 $a$와 $b$를 연결한 문자열(문자열 $a$의 끝에 문자열 $b$를 덧붙인 것)의 해시를 계산해야 한다면, $b$의 해시에 $k^{|a|}$를 곱한 뒤 $a$의 해시와 더하기만 하면 됩니다.
$$ h(ab) = h(a) + k^{|a|} \cdot h(b) $$ 문자열의 접두사는 다음과 같이 제거할 수 있습니다. $$ h(b) = \frac{h(ab) - h(a)}{k^{|a|}} $$ 접미사는 더 간단합니다: $$ h(a) = h(ab) - k^{|a|} \cdot h(b) $$문제에서는 $k$의 거듭제곱을 곱해야 하는 경우가 많으므로, 필요한 모든 거듭제곱을 미리 계산하여 배열에 저장해 두는 것이 좋습니다:
const int maxn = 1e5+5;
int p[maxn];
p[0] = 1;
for (int i = 1; i < maxn; i++)
p[i] = (1ll * p[i-1] * k) % mod; // аккуратно с переполнением
이것을 실제 문제에서는 어떻게 사용합니까? 하나의 큰 문자열에서 임의의 두 부분 문자열이 같은지 확인하는 쿼리에 답해야 한다고 합시다. 각 접두사에 대해 해시 함수의 값을 계산합시다.
int h[maxn];
h[0] = 0; // h[k] -- хеш префикса длины k
// будем считать, что s это уже последовательность int-ов
for (int i = 0; i < n; i++)
h[i+1] = (h[i] + p[i] * s[i]) % mod;
이제 이 접두사 해시를 이용하여 임의의 부분 구간에 대한 해시를 계산하는 함수를 정의할 수 있습니다:
$$ h(s[l:r]) = \frac{h_r-h_l}{k^l} $$모듈러 나눗셈은 특정한 k와 mod에 대해서만(정확히는 서로소인 경우에만) 할 수 있습니다. 어쨌든 이를 구현하는 데는 시간이 오래 걸리므로, 우리는 그렇게 하고 싶지 않습니다.
우리 문제에서는 꼭 다항식 해시를 얻는 것이 중요하지 않습니다. 중요한 것은 우리의 함수가 같은 부분 문자열에 대해 같은 다항식을 반환하는 것입니다. 0차로 맞추는 대신 다항식을 충분히 큰 어떤 차수, 예를 들어 $n$차로 맞춥시다.
$$ \hat{h}(s[l:r]) = k^{n-l} (h_r-h_l) $$이렇게 하는 편이 더 간단합니다. 이제 나누는 대신 곱하기만 하면 됩니다:
int hash_substring(int l, int r) {
return (h[r+1] - h[l]) * p[n-l] % mod;
}
이제 두 구간에 대해 이 함수를 호출하여 수치 값을 비교하기만 하면 되므로, 쿼리에 $O(1)$에 답할 수 있습니다.
연습 문제. 같은 것을 역방향 다항식 해시를 사용하여 작성해 보십시오. 이 방법도 충분히 쓸 만하며, 경우에 따라서는 오히려 더 간단합니다. 부분 문자열의 역방향 해시는 나눗셈이 필요 없으므로, 보통 정의에 나온 표준 형태 그대로 계산하고 사용합니다.
꿀팁. 작은 알파벳으로 이루어진 짧은 문자열의 역방향 다항식 해시를 $k=10$으로 잡으면, 문자열 해시의 수치 값이 문자열 자체와 한눈에 대응되어 보입니다.
$$ h(abacaba)=1213121 $$이 성질은 디버깅할 때 유용하게 활용할 수 있습니다.
#문제 예시
서로 다른 부분 문자열의 개수. 모든 부분 문자열의 해시를 $O(n^2)$에 계산하고 이를 모두 std::set에 추가합시다. 답을 구하려면 set.size()를 호출하기만 하면 됩니다.
문자열에서 부분 문자열 찾기. 패턴(찾으려는 문자열)의 해시를 계산한 뒤, 현재 부분 문자열의 해시를 유지하면서 패턴 크기의 “윈도우"를 텍스트 위로 이동시킬 수 있습니다. 이러한 부분 문자열 중 어느 하나의 해시가 패턴의 해시와 일치하면 원하는 부분 문자열을 찾은 것입니다. 이를 라빈-카프 알고리즘이라고 합니다.
같음 여부뿐 아니라 대소 관계까지 판단하는 부분 문자열 비교입니다. 임의의 두 문자열에는 어떤 공통 접두사가 있습니다(비어 있을 수도 있습니다). 그 길이에 대해 이진 탐색을 수행한 다음, 두 부분 문자열에서 공통 접두사 바로 뒤에 오는 문자를 가져와 비교합시다. 이 방법은 $O(\log n)$에 동작합니다.
부분 문자열의 팰린드롬 여부. 역방향 해시와 정방향 해시, 두 개의 배열을 계산해 둘 수 있습니다. 팰린드롬인지 확인하려면 첫 번째 배열과 두 번째 배열에서 hash_substring() 값을 각각 구해 비교하면 됩니다.
팰린드롬의 개수. 팰린드롬의 중심을 모두 순회하면서, 각 중심마다 이진 탐색으로 그 크기를 구할 수 있습니다. 부분 문자열이 팰린드롬인지 확인하는 방법은 이미 알고 있습니다. 팰린드롬 문제에서 늘 그렇듯이, 길이가 짝수인 팰린드롬과 홀수인 팰린드롬의 경우는 따로 처리해야 합니다. 이 방법은 $O(n \log n)$에 동작하지만, 이 문제는 선형 시간에도 풀 수 있습니다.