週刊 spaghetti_source

Rolling Hashing

18:57

文字列系の問題に対するインチキ・データ構造を紹介します．

Rolling Hashing

文字列 s = s[0,n) に対してハッシュ値を次のように対応させます：

　h(s) := (s[n-1] + p s[n-2] + ... + p^{n-1} s[0]) mod M

つまり文字列を p 進数表示だと思って mod M で値をとったものです．Rolling Hashing とは，すべてのプレフィックス（もしくはサフィックス）に対してこの値を計算することをいいます：

　phash[k] := h( s[0,k) ) for k = 0, ..., n

ここで p と M は互いに素な数を選びます．以下では p = 10^9+7，M = 2^64 に選びます．

Rolling Hashingで得られるテーブルを Rolling Hash Table ということがあります．また，Prefix Hash とか（これは同名があってヤヤコシイ），Sequence Hashと呼ばれることもあります．

部分文字列に対するハッシュ値計算

すべてのプレフィクスに対してハッシュ値を計算するのは普通に前から計算するだけです．そのテーブルがあれば，任意の部分文字列に対するハッシュも h(s[i,j)) = h(s[0,j)) - h(s[0,i)) * p^{j-i} として計算できます．p^{k} をすべての k について前計算しておけば h(s[i,j)) も O(1) です．

  static const ULL p = 1000000007ULL;
  string s;
  int n;
  vector<ULL> pow, phash;
  RollingHash(string s) : s(s), n(s.size()), pow(n+1), phash(n+1) {
    pow[0] = 1; phash[0] = 0;
    REP(i, n) {
      phash[i+1] = s[i] + phash[i] * p;
      pow[i+1] = pow[i] * p;
    }
  }

...

で，何ができるの？

ハッシュ値の衝突を無視すると，部分文字列同士の一致比較が O(1) できます．

いわゆるsuffix arrayが部分文字列の大小比較が O(1) でできる構造なので，rolling hash tableは劣化版suffix arrayだと思って良いかと思います．出来ることも基本的にニア・イコール．メリットは実装の簡素さにあります．

文字列検索（Rabin-Karp）

パターンの hash を計算して，テキストの前から順番に hash 値を比較するだけ（Rolling Hash で前計算しておく）．この手続きはRabin-Karpとして文字列検索では良く知られています．普通の文字列検索ではKnuth-Morris-PrattやBoyer-Mooreがあるのであまり使いませんが，基本事項です．

  ULL hash(string t) {
    ULL h = 0;
    REP(i, t.size()) h = t[i] + h * p;
    return h;
  }
  int find(string t) {
    int w = t.size(), count = 0;
    ULL h = hash(t);
    REP(i, n-w+1) if (hash(i, i+w) == h) {
      ++count; /* found */ 
    }
    return count;
  }

最長共通接頭語：lcp(i,j) の計算

LCPの計算は，普通なら suffix array を作る際に O(n) で追加のテーブルを作っておいて RMQ を使って O(1) で計算するんだ！というところですが，rolling hashing を使っても O(log n) で計算できます．すなわち，lcp(i,j) は s[i,i+k) == s[j,j+k) を満たす最大の k なので，これを二分探索します．

  int lcp(int i, int j) {
    int l = 0, r = min(n-i, n-j)+1;
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if (hash(i,i+m) == hash(j,j+m)) l = m;
      else                            r = m;
    }
    return l;
  }

Suffix Arrayの計算

k = lcp(i,j) とすると，s[i,n) と s[j,n) の大小関係は s[i+k] と s[j+k] の大小関係に一致します．なので，コレを operator < に採用して sort するだけで suffix array が作れます．計算量は O(n (log n)^2)．定数が小さいのがポイント．

struct RollingHash {
  // ...
  bool operator()(int i, int j) { 
    int k = lcp(i, j);
    return i+k >= n ? true : j+k >= n ? false : s[i+k] <= s[j+k];
  }
  // ...
};

  RollingHash R(s);
  int n = s.size();
  vector<int> sa(n);
  REP(i,n) sa[i] = i;
  sort(ALL(sa), R);

最長回文

部分文字列 t のうち t == rev(t) が成り立つ最長のものを求める問題を考えます．

簡単のため奇数長の回文に限ります．すると，長さ k の回文があれば長さ k-2 の回文もあるので，「最長回文の長さ」を二分探索できるようになります（偶数長への対応は間にダミーを挟むなどで可能）．

長さ k の回文があるか，という質問は，O(n) で長さ k の部分列のハッシュを全部表に登録しておいて，reverse(s) の長さ k の部分列を O(n) で見てハッシュで一致するものがあるかを調べます．全体で O(n log n)．

最長k出現部分列

部分文字列の中で k 回以上出現するもののうち，最も長いものを求める問題を考えます．

問題を反転して，長さ m の文字列のなかで最も出現回数が多いものの回数を f(m) とおくと，f(m) は m に関する単調減少関数なので，m に関する二分探索で f(m) >= k なる最大の m を求めるのが全体的方針．

f(m) の計算は長さ m の部分文字列のハッシュ値を全部テーブルに突っ込みつつ頻度の max をとるだけ．

...

このように，割と単純な手続きで色々と高効率なものが作れます．特に suffix array よりもだいたい実装が軽くなるのでオススメです．