문자열 해싱¶

해싱 알고리즘은 많은 문제를 해결하는 데 유용합니다.

우리는 문자열을 효율적으로 비교하는 문제를 해결하고자 합니다. 이를 위한 무차별 대입 방법은 단순히 두 문자열의 글자를 비교하는 것인데, 두 문자열의 크기를 $n_1$과 $n_2$라고 하면 시간 복잡도는 $O(\min(n_1, n_2))$입니다. 우리는 이보다 더 나은 방법을 원합니다. 문자열 해싱의 기본 아이디어는 다음과 같습니다: 각 문자열을 정수로 대응시키고, 문자열 대신 그 정수들을 비교합니다. 이렇게 하면 문자열 비교의 실행 시간을 $O(1)$로 줄일 수 있습니다.

이 변환을 위해서는 이른바 해시 함수가 필요합니다. 해시 함수의 목적은 문자열을 정수, 즉 이른바 문자열의 해시로 변환하는 것입니다. 다음 조건이 반드시 성립해야 합니다: 두 문자열 $s$와 $t$가 같다면($s = t$), 그 해시도 같아야 합니다($\text{hash}(s) = \text{hash}(t)$). 그렇지 않으면 문자열을 비교할 수 없습니다.

반대 방향은 성립하지 않아도 된다는 점에 주의하십시오. 해시가 같더라도($\text{hash}(s) = \text{hash}(t)$) 문자열이 반드시 같을 필요는 없습니다. 예를 들어, 모든 $s$에 대해 단순히 $\text{hash}(s) = 0$인 함수도 유효한 해시 함수입니다. 물론 이 함수는 전혀 쓸모가 없으므로 어리석은 예시에 불과하지만, 유효한 해시 함수인 것은 맞습니다. 반대 방향이 성립하지 않아도 되는 이유는 문자열이 지수적으로 많기 때문입니다. 이 해시 함수가 길이가 15 미만이고 소문자로만 이루어진 모든 문자열을 구별하기만 하면 된다고 해도, 그런 문자열이 너무 많기 때문에 해시는 이미 64비트 정수(예: unsigned long long)에 더 이상 들어가지 않습니다. 그리고 당연히 임의로 긴 정수를 비교하고 싶지는 않은데, 그렇게 하면 역시 $O(n)$의 복잡도가 되기 때문입니다.

따라서 보통은 해시 함수가 문자열을 고정된 범위 $[0, m)$의 수로 대응시키도록 하며, 그러면 문자열 비교는 고정된 길이를 가진 두 정수의 비교에 불과하게 됩니다. 그리고 당연히 $s \neq t$이면 $\text{hash}(s) \neq \text{hash}(t)$일 가능성이 매우 높기를 바랍니다.

이것이 반드시 기억해야 할 중요한 부분입니다. 완전히 다른 두 문자열이 같은 해시를 가질 수 있으므로(해시 충돌), 해싱을 사용하는 방법은 100% 결정적으로 정확하지는 않습니다. 하지만 서로 다른 두 문자열의 해시가 충돌할 확률은 여전히 매우 작기 때문에, 대다수의 문제에서는 이를 안전하게 무시할 수 있습니다. 그리고 이 글에서는 충돌 확률을 매우 낮게 유지하는 몇 가지 기법을 다룹니다.

문자열의 해시 계산¶

길이가 $n$인 문자열 $s$의 해시를 정의하는 좋고 널리 쓰이는 방법은 다음과 같습니다.

$$\begin{align} \text{hash}(s) &= s[0] + s[1] \cdot p + s[2] \cdot p^2 + ... + s[n-1] \cdot p^{n-1} \mod m \\ &= \sum_{i=0}^{n-1} s[i] \cdot p^i \mod m, \end{align}$$

여기서 $p$와 $m$은 적절히 선택한 양수입니다. 이를 다항식 롤링 해시 함수라고 합니다.

$p$는 입력 알파벳의 문자 수와 대략 같은 소수로 정하는 것이 합리적입니다. 예를 들어 입력이 영어 알파벳 소문자로만 이루어져 있다면 $p = 31$이 좋은 선택입니다. 입력에 대문자와 소문자가 모두 포함될 수 있다면 $p = 53$을 선택할 수 있습니다. 이 글의 코드에서는 $p = 31$을 사용합니다.

무작위로 고른 두 문자열이 충돌할 확률은 약 $\approx \frac{1}{m}$이므로, 당연히 $m$은 큰 수여야 합니다. $m = 2^{64}$을 선택하는 경우도 있는데, 이때는 64비트 정수의 정수 오버플로가 나머지 연산과 정확히 같게 동작하기 때문입니다. 하지만 충돌하는 문자열을 생성하는 방법이 존재합니다(이 방법은 $p$의 선택과 무관하게 동작합니다). 따라서 실전에서는 $m = 2^{64}$를 권장하지 않습니다. $m$으로는 어떤 큰 소수를 고르는 것이 좋습니다. 이 글의 코드에서는 단순히 $m = 10^9+9$를 사용합니다. 이 값은 큰 수이지만, 두 값의 곱셈을 64비트 정수로 수행할 수 있을 만큼은 충분히 작습니다.

다음은 소문자로만 이루어진 문자열 $s$의 해시를 계산하는 예시입니다. $s$의 각 문자를 정수로 변환합니다. 여기서는 $a \rightarrow 1$, $b \rightarrow 2$, $\dots$, $z \rightarrow 26$으로 변환합니다. $a \rightarrow 0$으로 변환하는 것은 좋은 생각이 아닙니다. 그렇게 하면 문자열 $a$, $aa$, $aaa$, $\dots$의 해시가 모두 $0$이 되기 때문입니다.

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

$p$의 거듭제곱을 미리 계산해 두면 성능이 향상될 수 있습니다.

예제 문제¶

문자열 배열에서 중복 문자열 찾기¶

문제: 길이가 각각 $m$자 이하인 $n$개의 문자열 $s_i$가 주어질 때, 중복된 문자열을 모두 찾아 그룹으로 나누십시오.

문자열을 정렬하는 자명한 알고리즘을 사용하면 시간 복잡도는 $O(n m \log n)$이 됩니다. 정렬에는 $O(n \log n)$번의 비교가 필요하고, 각 비교에 $O(m)$의 시간이 걸리기 때문입니다. 하지만 해시를 사용하면 비교 시간을 $O(1)$로 줄일 수 있으므로, $O(n m + n \log n)$ 시간에 동작하는 알고리즘을 얻습니다.

각 문자열의 해시를 계산하고, 해시를 인덱스와 함께 정렬한 다음, 해시가 같은 인덱스끼리 그룹으로 묶습니다.

vector<vector<int>> group_identical_strings(vector<string> const& s) {
    int n = s.size();
    vector<pair<long long, int>> hashes(n);
    for (int i = 0; i < n; i++)
        hashes[i] = {compute_hash(s[i]), i};

    sort(hashes.begin(), hashes.end());

    vector<vector<int>> groups;
    for (int i = 0; i < n; i++) {
        if (i == 0 || hashes[i].first != hashes[i-1].first)
            groups.emplace_back();
        groups.back().push_back(hashes[i].second);
    }
    return groups;
}

주어진 문자열의 부분 문자열 해시를 빠르게 계산하기¶

문제: 문자열 $s$와 인덱스 $i$, $j$가 주어질 때, 부분 문자열 $s [i \dots j]$의 해시를 구하십시오.

정의에 따라 다음이 성립합니다:

$$\text{hash}(s[i \dots j]) = \sum_{k = i}^j s[k] \cdot p^{k-i} \mod m$$

$p^i$를 곱하면 다음을 얻습니다:

$$\begin{align} \text{hash}(s[i \dots j]) \cdot p^i &= \sum_{k = i}^j s[k] \cdot p^k \mod m \\ &= \text{hash}(s[0 \dots j]) - \text{hash}(s[0 \dots i-1]) \mod m \end{align}$$

따라서 문자열 $s$의 각 접두사의 해시 값을 알고 있으면, 이 식을 이용해 임의의 부분 문자열의 해시를 바로 계산할 수 있습니다. 이를 계산할 때 부딪히는 유일한 문제는 $\text{hash}(s[0 \dots j]) - \text{hash}(s[0 \dots i-1])$을 $p^i$로 나눌 수 있어야 한다는 점입니다. 따라서 $p^i$의 모듈러 곱셈 역원을 구한 다음, 이 역원을 곱해야 합니다. 모든 $p^i$의 역원을 미리 계산해 둘 수 있으며, 이렇게 하면 $s$의 임의의 부분 문자열의 해시를 $O(1)$ 시간에 계산할 수 있습니다.

하지만 더 쉬운 방법도 존재합니다. 대부분의 경우, 부분 문자열의 해시를 정확히 계산하는 대신 $p$의 어떤 거듭제곱이 곱해진 해시를 계산하는 것으로 충분합니다. 두 부분 문자열의 해시 두 개가 있고, 하나에는 $p^i$가, 다른 하나에는 $p^j$가 곱해져 있다고 가정합시다. $i < j$이면 첫 번째 해시에 $p^{j-i}$를 곱하고, 그렇지 않으면 두 번째 해시에 $p^{i-j}$를 곱합니다. 이렇게 하면 두 해시 모두에 $p$의 같은 거듭제곱($i$와 $j$ 중 최댓값)이 곱해진 상태가 되므로, 이제 나눗셈 없이도 두 해시를 쉽게 비교할 수 있습니다.

해싱의 응용¶

다음은 해싱의 대표적인 활용 예입니다:

문자열에서 $O(n)$ 시간에 패턴 매칭을 수행하는 라빈-카프 알고리즘
문자열의 서로 다른 부분 문자열 개수를 $O(n^2)$에 계산하기(아래 참조)
문자열의 회문 부분 문자열 개수 계산하기.

문자열에서 서로 다른 부분 문자열의 개수 구하기¶

문제: 영어 소문자로만 이루어진 길이 $n$의 문자열 $s$가 주어질 때, 이 문자열의 서로 다른 부분 문자열의 개수를 구하십시오.

이 문제를 풀기 위해 모든 부분 문자열 길이 $l = 1 \dots n$에 대해 반복합니다. 각 부분 문자열 길이 $l$마다, 길이가 $l$인 모든 부분 문자열의 해시에 같은 $p$의 거듭제곱을 곱한 값들로 배열을 만듭니다. 배열에 있는 서로 다른 원소의 개수는 문자열에서 길이가 $l$인 서로 다른 부분 문자열의 개수와 같습니다. 이 개수를 최종 답에 더합니다.

편의상 $h[i]$를 $i$개의 문자로 이루어진 접두사의 해시로 사용하고, $h[0] = 0$으로 정의합니다.

int count_unique_substrings(string const& s) {
    int n = s.size();

    const int p = 31;
    const int m = 1e9 + 9;
    vector<long long> p_pow(n);
    p_pow[0] = 1;
    for (int i = 1; i < n; i++)
        p_pow[i] = (p_pow[i-1] * p) % m;

    vector<long long> h(n + 1, 0);
    for (int i = 0; i < n; i++)
        h[i+1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;

    int cnt = 0;
    for (int l = 1; l <= n; l++) {
        unordered_set<long long> hs;
        for (int i = 0; i <= n - l; i++) {
            long long cur_h = (h[i + l] + m - h[i]) % m;
            cur_h = (cur_h * p_pow[n-i-1]) % m;
            hs.insert(cur_h);
        }
        cnt += hs.size();
    }
    return cnt;
}

$O(n^2)$이 이 문제에서 가능한 최선의 시간 복잡도는 아니라는 점에 유의하십시오. $O(n \log n)$ 풀이는 접미사 배열에 관한 글에 설명되어 있으며, 접미사 트리나 접미사 오토마톤을 사용하면 $O(n)$에 계산하는 것도 가능합니다.

충돌이 일어나지 않을 확률 높이기¶

대부분의 경우 앞서 언급한 다항식 해시로 충분하며, 테스트 중에 충돌이 일어나지 않습니다. 충돌이 일어날 확률은 $\approx \frac{1}{m}$에 불과하다는 점을 기억하십시오. $m = 10^9 + 9$이면 확률은 $\approx 10^{-9}$로, 상당히 낮습니다. 하지만 이는 비교를 한 번만 했을 때라는 점에 유의하십시오. 문자열 $s$를 $10^6$개의 서로 다른 문자열과 비교한다면 어떻게 되겠습니까? 이 경우 적어도 한 번 충돌이 일어날 확률은 $\approx 10^{-3}$입니다. 그리고 $10^6$개의 서로 다른 문자열을 서로 비교하려 한다면(예를 들어 고유한 문자열이 몇 개인지 세는 경우), 적어도 한 번 충돌이 일어날 확률은 이미 $\approx 1$입니다. 이 작업은 충돌로 끝나 잘못된 결과를 반환하는 것이 거의 확실합니다.

더 나은 확률을 얻을 수 있는 아주 쉬운 요령이 있습니다. 각 문자열에 대해 서로 다른 해시 두 개를 계산하고(서로 다른 $p$ 두 개 및/또는 서로 다른 $m$을 사용하여), 대신 이 쌍을 비교하면 됩니다. 두 해시 함수 각각의 $m$이 약 $10^9$이라면, 이는 $m \approx 10^{18}$인 해시 함수 하나를 사용하는 것과 거의 같습니다. 이제 $10^6$개의 문자열을 서로 비교할 때 적어도 한 번 충돌이 일어날 확률은 $\approx 10^{-6}$으로 줄어듭니다.