概要

Rolling Hashは文字列 \(S\) のハッシュによって文字列比較を高速に行う。

ハッシュは衝突する可能性もある。衝突させにくくするには、複数のハッシュを計算して比較する等をすればよい。

計算量

  • 構築: \(O(|S|)\)

  • ハッシュ計算: \(O(1)\)

実装

#include<string>
using namespace std;
using ll = long long;

#define L 1000004

class RollingHash {
  ll base, mod;
  ll ptable[L];
  ll h[L];
  int sz;
public:
  RollingHash(string s, ll base, ll mod) : base(base), mod(mod) {
    sz = s.length();
    h[0] = 0;
    for(int i=0; i<sz; ++i) {
      h[i+1] = (h[i] * base + s[i]) % mod;
    }
    ptable[0] = 1;
    for(int i=0; i<sz; ++i) {
      ptable[i+1] = (ptable[i] * base) % mod;
    }
  }

  ll get(int l, int r) {
    // assert(0 <= l && r <= sz && l <= r);
    return (h[r] + ((mod - h[l]) * ptable[r-l] % mod)) % mod;
  }
};

Verified

  • AOJ: "ALDS1_14_B: String Search - String Search": source (C++14, 0.96sec)

戻る