라빈-카프와 부분문자열 쿼리

https://codeiiest-dev.github.io/Algorithms/String_Processing/String_Hashing/String_Hashing.html

문자열 s의 해시값은 위 해시 함수로 $O(|s|)$에 구할 수 있다.

using ll = long long;
using pll = pair<ll, ll>;

const ll X = 131, md1 = 1e9+7, md2 = 1e9+9;

pll hs(string &s) {
  pll H = { 0, 0 };
  for (int i = 0; i < s.size(); ++i) {
    auto &[a, b] = H;
    a = (a * X + s[i]) % md1;
    b = (b * X + s[i]) % md2;
  }
  return H;
}

 

길이가 $L (L \le |s|)$인 모든 부분문자열들의 해시값 역시 라빈-카프 알고리즘으로 $O(|s|)$에 구할 수 있다.

 

#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const ll X = 131, md1 = 1e9+7, md2 = 1e9+9;

string s = "pxichxijch";
int L = 5;
pll s_hash = { 0, 0 }, drop = { 1, 1 };

int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  // calc prefix
  for (int i = 0; i < L; ++i) {
    auto &[a, b] = drop;
    a = (a * X) % md1;
    b = (b * X) % md2;
  }
  
  // rabin-karp
  for (int i = 0; i < (int)s.size(); ++i) {
    auto &[a, b] = s_hash;
    a = (a * X + s[i]) % md1;
    b = (b * X + s[i]) % md2;
    if (i + 1 >= L) cout << a << ' ' << b << '\n';
    if (i >= L) {
      a = (md1 + a - (drop.first * s[i - L]) % md1) % md1;
      b = (md2 + b - (drop.second * s[i - L]) % md2) % md2;
    }
  }
  
}

 

같은 원리로, $O(|s|)$ 전처리를 통해 부분 문자열 $x =s[l\dotsc r] = s_{l} s_ {l+1} \dotsi s_{r}$의 해시값을 $O(1)$에 구할 수 있다.

 

#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const ll X = 131, md1 = 1e9+7, md2 = 1e9+9;

string s = "$pxichxijch";
pll drop[20], hashed[20];

int main() {

  // calc prefix
  drop[0] = { 1, 1 };
  for (int i = 1; i <= (int)s.size(); ++i) {
    drop[i] = { drop[i-1].first * X, drop[i-1].second * X };
    drop[i] = { drop[i].first % md1, drop[i].second % md2 };
  }

  // calc hash
  for (int i = 1; i < (int)s.size(); ++i) {
    hashed[i] = {
      (hashed[i-1].first * X + s[i]) % md1,
      (hashed[i-1].second * X + s[i]) % md2
    };
  }
  
  // query
  for (int l, r; cin >> l >> r; ) {
    cout
    << (md1 + hashed[r].first - (hashed[l-1].first * drop[r-l+1].first) % md1) % md1
    << ' '
    << (md2 + hashed[r].second - (hashed[l-1].second * drop[r-l+1].second) % md2) % md2
    << '\n';
  }
  
}

 

가능한 이유를 알아보자.

부분문자열 $x = s[l \dotsc r]$의 해시값은 $hash(s[1 \dotsc r])$의 suffix(비슷한것)임을 알 수 있다.

그렇다면 suffix를 제외한 나머지 부분(prefix라 하자)은 $hash(s[1 \dotsc l-1]) \times p^{|x|}$이다.

prefix + suffix = $hash(s[1 \dotsc r])$ 이므로 필요한 suffix는 $hash(s[1 \dotsc r])$ - prefix로 구할 수 있다.

 

당연한 이야기를 길게 한 이유는 이걸 몰라서 아래 문제에게 고통받았기 때문이다.

끝.