Rabin-Karp Pattern Matching

Rabin-Karp 알고리즘

라빈 카프 알고리즘은 문자열에 대해 해싱(Hashing)기법을 이용해 $O(N)$에 원하는 문자가 포함되어 있는지를 찾는 알고리즘이다.

꼭 문자열 문제가 아니더라도 연속된 배열이나 구간에 대해 해싱값이 필요한 경우 해당 알고리즘에서 사용하는 기법인 Rabin Fingerprint 식으로 해시를 구성하면 어떤 패턴이 존재하는지 빠르게 판별이 가능하다.

시간복잡도

여타 문자열 매칭 알고리즘이 그러듯이, 찾으려는 문자열이 $T$이고 원래 문자열이 $S$라면 $O(\lvert S \rvert + \lvert T \rvert)$로 탐색이 가능하다.

하지만 라빈 카프 알고리즘의 경우 특성상 모듈러 연산이 많이 포함되어 약간 상수가 붙는 편이다.

Rabin fingerprint

라빈 카프 알고리즘에서는 문자열에 대한 해시를 다음과 같은 방법으로 구성한다.

$H(s,\,i,\,m)$ 을 문자열 $s$에서 $i$번째 인덱스부터 시작하는 $m$길이의 부분 문자열에 대한 해시값이라고 한다면

$$ H(s,\,i,\,m)=s_i\cdot base^{m-1}+s_{i+1}\cdot base^{m-2}+...+s_{i+m-1} $$

위 식에서 $\rm base$는 특정 고정된 수(보통 작은 소수)로 정한다.

수가 너무 커지면 오버플로우가 일어나기 때문에 큰 소수로 모듈러를 취하기도 한다.

$s_i$ 자체가 의미하는 값은 아스키 코드라면 ‘a’ 값 그대로 써줄 수도 있고 특정 문자열이나 배열의 값을 의미하는 값을 적절히 설정하면 된다.

또한 해시값을 어떻게 구성할거냐에 따라 아래와 같이 부분 문자열에서 가장 앞 부분이 $base$의 승수가 가장 작게 설정하기도 한다.

두 가지 경우가 각각 어떻게 구현되는지 살펴볼 것이다.

$$ H(s,\,i,\,m)=s_i+s_{i+1}\cdot base+...+s_{i+m-1}\cdot base^{m-1} $$

Method 1 - Rolling Hash

$\quad H(s,\,i,\,m)=s_i\cdot base^{m-1}+s_{i+1}\cdot base^{m-2}+…+s_{i+m-1}$

라는 식과 $i+1$ 부터 시작하는 $m$길이의 해시

$\quad H(s,\,i+1,\,m)=s_{i+1}\cdot base^{m-1}+s_{i+2}\cdot base^{m-2}+…+s_{i+m}$

를 비교해보면,

$\quad H(s,\,i+1,\,m) = \left\{H(s,\,i,\,m) - s_i\cdot base^{m-1} \right\} \cdot base+s_{i+m} $

임을 알 수 있다. 따라서 $O(m)$ 으로 $i=0$ 에서 해시값을 미리 계산해두면 $i=1$ 부터 해시값이 필요한 가장 첫 인덱스까지 각 인덱스당 $O(1)$에 구성이 가능하다.

이 경우, Rabin fingerprint가 가장 앞의 문자가 가장 큰 $base$의 승수가 붙도록 설계되는데, 그렇지 않다고 하면 다음 해쉬를 만들 때 $base$를 곱하는게 아닌 나눠야해서 구현상 어려워지기 때문이다.

구현 - Rolling Hash

BOJ 1786 - 찾기

문자열 패턴 매칭의 가장 기본 문제인 이 문제를 Rolling hash를 이용해 구현해보자.

BASE에 대한 거듭제곱인 POWER 함수를 적절히 전처리 해준다음에 사용한다.

// 167, 227, 401
const int BASE = 401, MOD = 1e9 + 7, MAX = 1e6 + 6;
int HASH, len, HASH2, POWER[MAX];

void solve() {
   POWER[0] = 1;
   for (int i = 1; i < MAX; i++) POWER[i] = md(MOD, POWER[i - 1] * BASE);

   string s, t;
   getline(cin, s);
   getline(cin, t);
   len = sz(t);
   if (sz(s) < len) {
      cout << 0;
      return;
   }
   for (int i = len - 1; i >= 0; i--) {
      HASH = md(MOD, HASH + t[i] * POWER[len - 1 - i]);
      HASH2 = md(MOD, HASH2 + s[i] * POWER[len - 1 - i]);
   }
   vi ans;
   if (HASH == HASH2) ans.pb(0);
   for (int i = 1; i + len - 1 < sz(s); i++) {
      HASH2 = md(MOD, md(MOD, HASH2 - s[i - 1] * POWER[len - 1]) * BASE + s[i + len - 1]);
      if (HASH == HASH2) ans.pb(i);
   }
   cout << sz(ans) << endl;
   for (int i: ans) cout << i + 1 << ' ';
}

Method 2 - Prefix sum array

위와 같이 Rolling Hash의 성질을 이용해서 각 인덱스마다 해쉬값을 구해 비교할 수도 있지만, 좀더 일반적인 방법은 구간합 배열을 이용하는 방법이다.

이 방법은 위에서 언급했던 Rabin-fingerprint의 또 다른 형태인 가장 작은 승수가 가장 문자열의 앞의 값과 곱해지는

$\quad H(s,\,i,\,m) = s_i+s_{i+1}\cdot base+…+s_{i+m-1}\cdot base^{m-1}$

과 같은 형태를 취하여 해시를 구성하는 것이 간편하다.

구현은 다음과 같다.

1. 찾으려는 문자열의 해시를 구성한다.

찾으려는 문자열 $T$의 길이 = $m$

$\quad H(T)=t_0+t_{i+1}\cdot base+…+t_{m-1}\cdot base^{m-1}$

와 같이 찾으려는 문자열에 대한 해시를 구성해둔다.

Rolling Hash 방법 때와 $base$의 곱해지는 방법이 반대가 되어있음을 확인하자.

2. 원래 문자열에서 구간합 배열을 거듭제곱 배열을 이용해 전처리한다.

for (int i = 0; i < n; i++)
   PSUM[i + 1] = md(MOD, PSUM[i] + POWER[i] * s[i]);

3. 두 해시를 곱 연산을 이용해 비교한다

$H(s,\,i,\,m)$이 $H(T)$와 같은지 살펴보자.

$\quad H(T) \qquad~\,= t_0+t_{i+1}\cdot base+…+t_{m-1}\cdot base^{m-1}$

$\quad H(S,\,i,\,m)=s_i\cdot base^i+s_{i+1}\cdot base^{i+1}+…+s_{i+m-1}\cdot base^{i+m-1}$

만약 두 구간이 일치하는 Hash를 갖는다면,

$\quad \dfrac{H(S,\,i,\,m)}{base^i}=H(T)$ 이여야 한다.

이는 나눗셈 연산을 곱셈 연산으로 바꾸어서 수행한다면

$\quad H(S,\,i,\,m)=H(T)\cdot base^i$ 를 검사해주면 된다.

4. 위에서 도출해낸 결론으로 각 인덱스당 비교를 $O(1)$에 해줄 수 있다.

vi ans;
for (int i = 0; i + m - 1 < n; i++)
   if (md(MOD, HASH * POWER[i]) == md(MOD, PSUM[i + m] - PSUM[i]))
      ans.pb(i);

전체 코드는 다음과 같다.

// 167, 227, 401
const int BASE = 401, MOD = 1e9 + 7, MAX = 1e6 + 6;
int HASH, HASH2, POWER[MAX], n, m, PSUM[MAX];

void solve() {
   POWER[0] = 1;
   for (int i = 1; i < MAX; i++) POWER[i] = md(MOD, POWER[i - 1] * BASE);

   string s, t;
   getline(cin, s);
   getline(cin, t);
   n = sz(s), m = sz(t);
   if (sz(s) < m) {
      cout << 0;
      return;
   }

   for (int i = 0; i < m; i++) HASH = md(MOD, HASH + POWER[i] * t[i]);
   for (int i = 0; i < n; i++)
      PSUM[i + 1] = md(MOD, PSUM[i] + POWER[i] * s[i]);

   vi ans;
   for (int i = 0; i + m - 1 < n; i++)
      if (md(MOD, HASH * POWER[i]) == md(MOD, PSUM[i + m] - PSUM[i]))
         ans.pb(i);

   cout << sz(ans) << endl;
   for (int i: ans) cout << i + 1 << ' ';
}

정확성 개선 - 다중 해시 검사

사실 해싱이라는게 해시 충돌을 절대 배제할 수 없는 알고리즘이기 때문에 테스트 데이터가 특정 해시를 저격하거나 정확성이 부족해서 WA가 나올 수 있다.

이 경우, $base$나 $modular$값을 여러개를 이용해서 각각 다른 상황에서 해시검사를 해보고 특정 인덱스 $i$에서 모두 매칭된다고 판단되면 매칭되는 것으로 판단하는 것으로 정확성을 올릴 수 있다.

물론 시간복잡도는 $N$중 해시를 쓰면 $N$배 증가하겠지만, 적당히 문제에 따라 사용할 수 있도록 한다.
다중 해시를 쓰지 않고도 $base$나 $modular$값을 바꾸는 것만으로도 테스트 케이스를 통과할 수 있는 결과가 될 수 있음도 유의한다.

이와 관련해서는 $base$를 바꾸는 3중 해시 코드를 쓰는 진한님의 문제 풀이 코드를 참고하면 된다.

2차원에서의 구간합 Rabin-Karp 패턴 매칭

이것도 가능하다.

이 문제는 원래 Aho-Corasick 알고리즘과 KMP를 적절히 섞어서 풀 수 있지만, 2차원 Rabin-Karp 원툴로 해결 가능하다.

BOJ 10538 빅 픽쳐 정리글