해싱

두 문자열이 같은 문자열인지 확인하려고 합니다.

 

물론 두 문자열의 길이만큼 직접 비교하는 식으로 확인할 수 있지만, 두 문자열의 해시값이 같은지 확인하는 방식으로도 확인할 수 있습니다.

 

해시 함수에는 다양한 종류가 있지만, 이 문제에 나오는 해시 함수를 이용합니다.

 

https://www.acmicpc.net/problem/15829

15829번: Hashing

 

---

라빈-카프 알고리즘(Rabin-Karp Algorithm)

 

어떤 문자열 \(S\)가 주어졌을 때, 이 문자열의 일정한 \(L\)길이의 모든 부분 문자열의 해시를 구해봅시다.

일반적으로는 \(O(L \cdot |S|)\)의 시간이 들겠지만, 위 해시 함수의 특성상 \(O(|S|)\)의 시간복잡도로 모든 해시값을 구할 수 있습니다.

 

\(S\)의 첫 \(L\)길이의 부분 문자열의 해시 값을 구해놨다고 가정해봅시다.

 

\(H_0 = S_1 \cdot r^{L-1} + S_2 \cdot r^{L-2} + \cdots + S_L \cdot r^0\)

 

이 다음 \(L\)길이의 부분 문자열의 해시 값은 다음과 같을 것입니다.

 

\(H_1 = S_2 \cdot r^{L-1} + S_3 \cdot r^{L-2} + \cdots + S_{L+1} \cdot r^0\)

 

이 식을 잘 관찰해보면 \(H_0\)에서 \(H_1\)을 쉽게 계산해 낼 수 있다는 사실을 알 수 있습니다.

 

\(H_1 = H_0 \cdot r - S_1 \cdot r^L + S_{L+1}\)

 

한 해시값에서 다음 해시값을 구하는데 \(O(1)\)의 시간밖에 들지 않으므로, 모든 부분 문자열의 해시값을 \(O(|S|)\)의 시간복잡도로 계산할 수 있습니다.

 

 

이를 이용해 문자열 검색도 \(O(|S| + |T|)\)에 할 수 있게 됩니다.

 

https://www.acmicpc.net/problem/1786

1786번: 찾기

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const ll M1 = 1e9 + 7;
const ll M2 = 1e9 + 9;
const ll MUL = 131;
 
string S, T;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    getline(cin, S);
    getline(cin, T);
 
    ll H1 = 0, H2 = 0;
    for (int i = 0; i < T.size(); i++)
    {
        H1 *= MUL, H2 *= MUL;
        H1 += T[i], H2 += T[i];
        H1 %= M1, H2 %= M2;
    }
 
    ll of1 = 1, of2 = 1;
    for (int i = 0; i < T.size(); i++)
    {
        of1 *= MUL, of2 *= MUL;
        of1 %= M1, of2 %= M2;
    }
 
    vector <int> ans;
 
    ll cH1 = 0, cH2 = 0;
    for (int i = 0; i < S.size(); i++)
    {
        cH1 *= MUL, cH2 *= MUL;
        cH1 += S[i], cH2 += S[i];
        cH1 %= M1, cH2 %= M2;
 
        if (i >= T.size())
        {
            cH1 += (M1 - of1 * S[i - T.size()] % M1) % M1;
            cH1 %= M1;
 
            cH2 += (M2 - of2 * S[i - T.size()] % M2) % M2;
            cH2 %= M2;
        }
 
        if (i >= T.size() - 1)
        {
            if (cH1 == H1 && cH2 == H2)
            {
                ans.push_back(i - T.size() + 2);
            }
        }
    }
 
    cout << ans.size() << '\n';
    for (int it : ans) cout << it << ' ';
}

모듈러 \(10^9+7, 10^9+9\) 두 가지에 대한 해시값을 각각 비교해서, 두 해시값이 모두 일치하면 같은 문자열이라고 판단했습니다.

---

해시 테이블은 원리가 간단하고 빠른 평균 시간복잡도를 보장해주지만, 서로 다른 두 자료가 같은 해시값을 갖게 되는 해시 충돌이 발생하게 되면 효율이 급감하게 되는 자료구조입니다.

 

해시 충돌을 방지하기 위해서는 다음과 같은 방법을 사용할 수 있습니다.

 

1. 해시 값이 같으면 실제 데이터도 같은지 이중으로 확인작업을 한다.

-> 답이 틀리진 않지만, 시간 초과를 받을 수 있습니다.

 

2. 서로 다른 여러 개의 해시값을 사용해 모든 해시값이 일치하면 같은 값이라고 가정한다.

-> 해시 충돌 확률이 매우 낮아지겠지만, 역시 임의로 저격 데이터를 만드는 경우까지는 막을 수 없습니다.

 

따라서 평균적인 랜덤 데이터를 처리할 때는 매우 효율적이지만, 특수한 경우가 많은 데이터를 처리할 때나 저격 데이터를 임의로 추가할 수 있는 경우(CodeForces, 백준 등) 에는 다른 대체 알고리즘을 이용하는 것이 더 좋을 수 있습니다.

 

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217