88. Rabin-Karp

라빈-카프 알고리즘(Rabin-Karp Algorithm)은 해싱을 이용하여 문자열을 검색하는 알고리즘이다. 이 알고리즘은 주로 부분 문자열들이 동일한지의 여부를 빠르게 판별해야 하는 경우에 쓰이는데, 각각의 부분 문자열을 일일히 해싱하는 것은 시간이 너무 오래 걸리므로 더 빠른 방법이 요구된다. Rabin Fingerprint는 이러한 문제를 해결할 수 있는 해싱 방법으로, 다음과 같은 형태로 나타낼 수 있다.

$$f(x, n) = \sum_{k=0}^n(s_k \cdot x^k) = s_0 + s_1x + s_2x^2 + \ldots + s_{n-1}x^{n-1} + s_nx^n$$

일반적인 라빈-카프 알고리즘은 이 식을 약간 변형해서 다음과 같이 만든 다음 해시값을 계산한다.

$$f(x, n) = \sum_{k=0}^n(s_k \cdot x^{n-k}) = s_0x^n + s_1x^{n-1} + s_2x^{n-2} + \ldots + s_{n-1}x + s_n$$

이 식을 그대로 계산하면 값이 너무 커지므로 적절한 모듈러를 설정해서 해시값을 정하는 것이 좋다. 그렇다면 왜 이 방법으로 해시값을 계산하는지를 알 필요가 있는데, 이것은 길이가 같은 부분 문자열의 해시값을 선형 시간에 구할 수 있다는 장점을 바탕으로 이해할 수 있다. 두 부분 문자열 $[s_l, s_r]$과 $[s_{l+1}, s_{r+1}]$을 Rabin Fingerprint 함수로 해싱한 결과는 기본적으로 다음과 같다.

$$v_1 = s_lx^{r-l} + s_{l+1}x^{r-l-1} + s_{l+2}x^{r-l-2} + \ldots + s_{r-1}x + s_r$$

$$v_2 = s_{l+1}x^{r-l} + s_{l+2}x^{r-l-1} + \ldots + s_{r-1}x^2 + s_rx + s_{r+1}$$

이때 $v_1$과 $v_2$를 다음과 같은 관계식으로 나타낼 수 있다.

$$v_2 = x(v_1 - s_lx^{r-l}) + s_{r+1} = xv_1 - s_lx^{r-l+1} + s_{r+1}$$

$x^{r-l}$이나 $x^{r-l+1}$은 문자열의 길이가 일정하면 변하지 않는 값이므로 미리 구해 놓을 수 있고, $l = 0$인 경우의 해시값을 구하면 같은 길이의 부분 문자열의 해시값을 선형 시간에 모두 구할 수 있게 된다. 또한 위의 식에서 $s_lx^{r-l+1}$을 빼는 과정을 생략한다면 부분 문자열 $[s_l, s_r]$의 해시값으로부터 부분 문자열 $[s_l, s_{r+1}]$의 해시값을 알아낼 수도 있다. 이것을 응용하면 $s$의 모든 접두사의 해시값을 선형 시간에 구한 다음 임의의 부분 문자열의 해시값을 빠르게 구할 수도 있다.

$$f(x, l-1) = s_0x^{l-1} + s_1x^{l-2} + \ldots + s_{l-2}x + s_{l-1}$$

$$f(x, r) = s_0x^r + s_1x^{r-1} + \ldots + s_{r-1}x + s_r$$

따라서 부분 문자열 $[s_l, s_r]$의 해시값은 다음과 같다.

$$v = f(x, r) - x^{r-l+1}f(x, l-1)$$

---

해시값을 구하기 전에 정해야 하는 값은 모듈러와 $x$인데, 이 값들이 너무 작으면 해시 충돌이 발생할 가능성이 높으므로 주의해야 한다. 모듈러는 $|s|^{2.5}$ 이상, $x$는 가능한 $s_i$의 범위보다 큰 값으로 설정하는 것을 권장한다. 또한 모듈러의 약수의 수가 적을수록, 모듈러와 $x$의 최대공약수가 작을수록 좋다. 해시 충돌이 발생할 가능성이 높을 경우 두 부분 문자열의 해시값이 같은 경우에 직접 문자열을 비교하는 과정이 필요할 수도 있지만 해시 충돌이 발생할 가능성이 거의 없는 경우 해시값이 같으면 단순 비교 없이 같은 문자열이라고 간주해도 틀릴 확률이 거의 없다는 장점이 존재한다.

---

구현은 다음과 같다. 계산 과정에서 오버플로우가 발생하지 않아야 하므로 __int128 자료형이 사용되었고, 아래 코드에서는 $x$를 $120$, 모듈러를 $10^{15}+37$로 설정했다. 이밖에 $10^{16}+61$, $10^{17}+3$, $10^{17}+13$, $10^{17}+19$, $10^{17}+21$, $10^{17}+49$, $10^{18}+3$, $10^{18}+9$, $10^{18}+31$ 등을 간단한 소수 모듈러로 사용할 수 있고, 꼭 소수가 아니어도 큰 소수 두 개의 곱으로 이루어진 경우 등 효율성이 높다면 모듈러로 사용해도 괜찮다. $10^{19}$ 정도 되는 모듈러는 __int128형으로 처리하면 계산 과정에서 오버플로우가 발생하지는 않지만, 모듈러를 signed long long형으로 저장하지 않도록 주의해야 한다. $1.3 \times 10^{19}$ 이상의 모듈러는 계산 과정에서 __int128 자료형으로도 오버플로우가 발생할 수 있으므로 사용하지 말자.

#import<bits/stdc++.h>
using namespace std;
__int128 mod = 1e15 + 37, x = 120, f[100005];
string s;
__int128 pow(__int128 x, __int128 y)
{
    __int128 s = 1;
    for(; y; y >>= 1)
    {
        if(y & 1)s = s * x % mod;
        x = x * x % mod;
    }
    return s;
}
__int128 hash(int l, int r)
{
    __int128 w = f[r] - (l ? f[l] : 0) * pow(x, r - l + 1) % mod;
    if(w < 0)w += mod;
    return w;
}
int main()
{
    cin >> s;
    int n = s.size();
    f[0] = s[0];
    for(int i = 1; i < n; i++)f[i] = (x * f[i - 1] + s[i]) % mod;
}

hash 함수는 부분 문자열 $[s_l, s_r]$의 해시값을 반환하는 함수이다. 하지만 이 함수를 직접 사용하는 경우는 그렇게 많지 않고, 길이가 일정한 부분 문자열의 해시값을 모두 구하는 경우가 훨씬 많을 것이다. 이것은 다음과 같이 구현할 수 있다.

#import<bits/stdc++.h>
using namespace std;
__int128 mod = 1e15 + 37, n, x = 120, f[100005];
string s;
vector<int>v;
__int128 pow(__int128 x, __int128 y)
{
    __int128 s = 1;
    for(; y; y >>= 1)
    {
        if(y & 1)s = s * x % mod;
        x = x * x % mod;
    }
    return s;
}
void H(int k)
{
    __int128 p = pow(x, k), w = f[k - 1];
    for(int i = k; i <= n; i++)
    {
        v.push_back(w);
        w = (x * (w - s[i - k] * p % mod + mod) + s[i]) % mod;
    }
}
int main()
{
    cin >> s;
    n = s.size();
    f[0] = s[0];
    for(int i = 1; i < n; i++)f[i] = (x * f[i - 1] + s[i]) % mod;
}

H 함수를 호출한 이후 벡터 $v$에 들어간 값이 모두 다르다면 길이가 $k$인 부분 문자열이 모두 다르고, 그렇지 않다면 길이가 $k$인 서로 같은 부분 문자열이 존재한다고 간주할 수 있다.

 

[연습문제]

 

BOJ 15829. Hashing (Bronze II)

Rabin Fingerprint 함수를 구현하는 문제이다. 이 문제에서 알 수 있듯 함수 구현 자체의 난이도는 브론즈인데, 이걸 응용하는 순간 난도가 쭉 올라간다.

 

BOJ 21559. 암호 찾기 (Platinum V)

두 문자열에서 길이가 $K$인 부분 문자열의 해시값을 모두 구한다. 양쪽 부분 문자열에서 공통으로 나타나는 해시값의 수가 답이 된다.

 

BOJ 3033. 가장 긴 문자열 (Platinum III)

길이가 $k$인 부분 문자열이 두 번 이상 등장했다면 길이가 $k$보다 작은 부분 문자열 중에도 두 번 이상 등장하는 것이 존재하고, 길이가 $k$인 부분 문자열이 모두 다르다면 길이가 $k$보다 큰 부분 문자열도 모두 다르다. 따라서 부분 문자열의 길이에 대한 이분 탐색으로 답을 구할 수 있다.

 

BOJ 21218. Unique Activities (Platinum II)

이번에는 한 번만 등장하는 부분 문자열을 찾아야 한다. 이 부분 문자열은 두 번 이상 등장하는 가장 긴 부분 문자열보다 한 글자 길기 때문에 3033번에서 사용한 이분 탐색을 그대로 사용할 수 있다. 해당하는 부분 문자열이 여러 개라면 인덱스가 가장 빠른 문자열을 찾으면 되는데 이걸 찾는 것은 어렵지 않다.

 

→ solved.ac tag: rabin_karp