Rabin fingerprint for problem solving

Rabin fingerprint란?

Rabin fingerprint는 길이 $n$ 의 배열 $m$ , 임의의 값 $x$ 에 대해 아래와 같은 수식을 가지는 일종의 해시 함수입니다.

f (x) = m_{0} + m_{1} x + \dots + m_{n - 1} x^{n - 1}

주로, 라빈카프 알고리즘에서 사용되기 때문에 해당 알고리즘을 공부하신 분께는 친숙할텐데요. 위 해시함수를 응용하여 문제를 해결하는 방법에 대해서 소개하고자 합니다. 모든 설명에서 $x$ 가 $m a x (m_{i})$ 보다 큰 상황을 가정합니다.

가장 긴 문자열(링크)

$m_{0}$ ~ $m_{i}$ 를 $g (x, 0, i) = m_{0} + m_{1} x + \dots + m_{i} x^{i}$ 와 같이

$m_{j}$ ~ $m_{j + i}$ 를 $g (x, j, j + i) = (m_{j} x^{j} + m_{j + 1} x^{j + 1} + \dots + m_{j + i} x^{j + i}) / x^{j}$ 와 같이 표현할 수 있습니다.

여기서, $g (x, 0, i) == g (x, j, j + i)$ 라면, $m_{0}$ ~ $m_{i}$ 와 $m_{j}$ ~ $m_{j + i}$ 는 같습니다.

$p_{i}$ 를 $g (x, 0, i)$ 라고 정의하고 배열 $p$ 를 미리 만들어둔다면, 두 부분 배열이 일치하는 지 $O (1)$ 만에 확인할 수 있게 됩니다. 따라서, 같은 해시값을 가지는 부분 문자열을 찾는 것으로 문제를 간단하게 바꿀 수 있습니다.

두 번 이상 등장하는 부분 문자열이 존재함을 1로, 존재하지 않음을 0으로 표현한다면, 부분 문자열의 길이 y에 대해 각 상태에 대한 표현값은 단조감소하게 됩니다. 따라서 문제에 이분탐색을 적용할 수 있습니다. 길이 y에 대해 겹치는 해시값이 존재함은 set과 같은 자료구조를 이용해 해결할 수 있습니다.

이를 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int BASE = 256; // x에 해당하는 값
const ll MOD[2] = {1000000007, 1000000009}; // 너무 큰 해시값을 관리하기 어려우므로 사용.
ll power[200001][2]; // x의 y제곱을 각 모듈로에 맞게 미리 계산
ll psum[200001][2]; // 해시값의 부분합 배열
int n;
char s[200002];

ll getHash(int i, int j) {
    ll ret[2];
    for (int k = 0; k < 2; k++) {
        ret[k] = (psum[j][k] - psum[i - 1][k] + MOD[k]) % MOD[k];
        ret[k] = ret[k] * power[n - i][k] % MOD[k]; // 적절한 power를 곱해 문자열 등장 위치를 보정한다.
    }

    return ret[0] * MOD[1] + ret[1]; // 두 모듈로에서 얻은 해시값을 조합.
}

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);

    power[0][0] = power[0][1] = 1;

    for (int i = 0; i < 2; i++)
        for (int j = 1; j <= n; j++) {
            power[j][i] = power[j - 1][i] * BASE % MOD[i];
            psum[j][i] = (psum[j - 1][i] + s[j] * power[j][i]) % MOD[i];
        }

    int l = 1, r = n, mid;
    unordered_set<ll> us;

    while (l <= r) {
        mid = (l + r) / 2;
        us.clear();

        int flag = 0;

        for (int i = 1; i <= n - mid + 1; i++) {
            ll temp = getHash(i, i + mid - 1);
            if (us.find(temp) != us.end()) {
                flag = 1;
                break;
            }
            us.insert(temp);
        }

        if (flag) l = mid + 1;
        else r = mid - 1;
    }
    printf("%d", r);
}

문자열과 쿼리(링크)

접미사는 생각하기가 까다로우므로, 문자열을 뒤집어서 가장 긴 공통 접두사를 찾는 것으로 합시다. 이는 Z알고리즘으로 문자열의 모든 위치 $i$ 에 대해 구할 수 있는 것이 알려져 있는데요. Rabin fingerprint 함수를 이용해도 쉽게 구할 수 있습니다. ‘가장 긴 문자열’ 문제와 동일하게 문자열에 대한 해시값 prefix sum 배열 $p$ 를 미리 만들어봅시다. 그러면 $S_{0} S_{1} S_{2} \dots S_{n - 1}$ 과 $S_{i} S_{i + 1} S_{i + 2} \dots S_{n - 1}$ 에 대해 가장 긴 공통 접두사의 길이는 이분탐색과 배열 $p$ 를 이용해 쉽게 해결할 수 있습니다. 이를, 각 쿼리마다 구해주는 것으로 문제를 해결할 수 있습니다.

마찬가지로, 찾기에서 사용되는 단순한 패텅매칭이나 LCS 같은 알고리즘까지 비슷한 방법으로 구할 수 있습니다. Problem solving에서 강력한 도구인 해시를 조금 더 응용해볼까요?

임의의 배열에 대한 해시값이 $f$ 일때, 어떤 원소의 삽입, 삭제, 변경 등의 연산이 적용된 해시값 $f^{'}$ 을 $O (l o g N)$ 에 구할 수 있습니다.

모든 원소 $i$ 에 대해 $m_{i} x^{i}$ 를 세그먼트 트리에 저장하고 관리해봅시다. 인덱스 $j$ 에 값 $y$ 를 삽입하는 연산은 기존의 $j$ ~ $n - 1$ 에 위치한 값들에 $x$ 를 곱하고 $y x^{j}$ 를 더하는 것으로 표현할 수 있습니다. 비슷한 방식으로 삭제, 변경 연산이 가능합니다.

또한, 삽입, 삭제, 변경과 같은 연산이 배열의 끝에서만 일어난다면 prefix sum을 관리함으로써 $O (1)$ 만에 계산할 수 있게 됩니다.

위 사실을 이용하여 풀 수 있는 문제를 소개하겠습니다.

Stack Exterminable Arrays(링크)

스택에 원소를 넣는데, 인접한 두 원소의 값이 같으면 두 원소는 사라지게 됩니다. 어떤 배열을 순서대로 스택에 넣었을 때 스택이 비어있는 상태로 끝이 나면 Stack Exterminable하다고 합니다. 이때, 주어진 배열에서 Stack Exterminable한 부분 배열의 개수를 찾는 문제입니다. 부분 배열 $a_{i}, a_{i + 1}, a_{i + 2}$ , …, $a_{j}$ 가 Stack Exterminable 하다는 것은 $a_{0}, a_{1}, \dots, a_{i - 1}$ 의 결과와 $a_{0}, a_{1}, \dots, a_{j}$ 의 결과스택이 일치한다는것과 동치입니다.

결과스택이 일치하는 지 여부는 어떻게 빠르게 판단할까요? 이때 사용되는 것이 해싱입니다. 결과스택은 하나의 수열로 표현될 것이므로 이에 대한 해시값을 각각 구해놓고 일치하는 지 판단하는 식입니다.

이를 구현한 코드입니다.

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
using namespace std;

typedef long long ll;
const int BASE = 300007;
const ll MOD[2] = { 1000000009, 1000000021 };
ll power[300001][2];

unordered_map<ll, int> um;
vector<int> v;

int main() {
    int tc;
    scanf("%d", &tc);

    power[0][0] = power[0][1] = 1;
    for (int i = 0; i < 2; i++)
        for (int j = 1; j <= 300000; j++)
            power[j][i] = power[j - 1][i] * BASE % MOD[i];

    while (tc--) {
        int n;
        scanf("%d", &n);

        um.clear();
        v.clear();

        ll ret[2] = {0};
        ll ans = 0;
        um[0]++;

        for (int i = 0; i < n; i++) {
            int t;
            int szz = sz(v);
            scanf("%d", &t);

            if (!v.empty() && v.back() == t) {
                for (int j = 0; j < 2; j++)
                    ret[j] = (ret[j] - t * power[szz - 1][j] % MOD[j] + MOD[j]) % MOD[j];
                v.pop_back();
            }
            else {
                for (int j = 0; j < 2; j++)
                    ret[j] = (ret[j] + t * power[szz][j]) % MOD[j];
                v.push_back(t);
            }

            ans += um[ret[0] * MOD[1] + ret[1]]++;
        }

        printf("%lld\n", ans);
    }
}

Laminar Family(링크)

$N$ 개의 정점을 가진 트리에서 $f$ 개의 경로가 주어집니다. 이 경로들 중 서로 엇갈리는 것이 있는 지 판단하는 문제입니다. 경로들을 각 경로의 길이가 긴 순서대로 정렬하고 이 순서대로 각 경로를 살펴봅시다. 경로들을 순서대로 보면서 각 정점마다 이 정점을 어떤 경로들이 지나갔는 지 기록해봅시다.

지금 보고 있는 경로에 존재하는 모든 정점에서 지났던 경로들의 집합이 전부 일치한다면, 이 경로와 엇갈리는 길이가 더 긴 경로는 존재하지 않습니다. 즉, 각 정점들의 경로 집합이 일치하는 지 판별해야 하며 이 집합을 해시값으로 나타낼 수 있습니다.

Heavy-light decomposition을 이용하면, 경로를 $O (l o g N)$ 개의 구간으로 나타낼 수 있으므로 세그먼트 트리에 각 집합의 정보를 담아서 관리하면 됩니다. 여기서 어느 구간에 속한 정점들의 집합에 원소를 하나 추가하는 연산은 lazy propagation으로 해당하는 경로에 대응되는 해시값을 업데이트 해주는 것으로 해결할 수 있습니다

Cow Patterns(링크)

$N$ 개의 수를 가지는 배열이 주어지고, 길이 $K$ 의 등수 패턴이 주어질 때 배열에서 등수 패턴으로 표현되는 부분 배열을 전부 구하는 문제입니다. 패턴에서 같은 수를 가지는 것들끼리 묶어서 그 수가 등장하는 위치의 집합을 해시로 표현해봅시다. $f (x)$ 를 배열 $x$ 의 Rabin fingerprint 해시값이라고 해봅시다. 만약 패턴이 $3 2 1 2 2 3 3 1$ 이라면, $p_{1} = f ([00100001])$ , $p_{2} = f ([01011000)]$ , $p_{3} = f ([10000110])$ 로 표현할 수 있을겁니다. 여기서 전체 패턴에 해당하는 해시값을 얻어내는 것은 쉽습니다. $1 p_{1} + 2 p_{2} + 3 p_{3}$ 가 되겠지요. 우리는 $p$ 를 관리함으로써 특정 값을 가지는 모든 수를 다른 값으로 치환하는 것을 쉽게 할 수 있게 되었습니다.

이제 모든 길이 $K$ 의 부분 배열을 검사하면서, 각 부분 배열에 해당하는 해시값과 치환된 등수패턴의 해시값을 비교하는 것으로 문제를 해결하시면 됩니다.

이상으로 글을 마치겠습니다.

읽어주셔서 감사합니다.