蟻本片手に学ぶアルゴリズム ~ローリングハッシュ~

導入

アドベントカレンダーを書けというサークル内の圧力に屈しました。
競技プログラマの間ではもはやバイブル的な位置にある蟻本から、気になったアルゴリズムを迷える子蟻たちになんちゃらかんちゃら（面倒になりました）。
サークルの後輩向けに書いているところもあるので少し冗長かも。端折りすぎたかも。

文字列検索の競プロでの位置付け

文字列検索は競技プログラミングでは中級以上（AtCoder400点~?）頻出の分野です。これはシンプルな問題設定で作りやすいこともあると思いますが、愚直な解法と有効なアルゴリズムでは実行時間に大きな差が出る操作であることの現れと言えます。

具体的なお話

イメージしやすいように問題を想定しましょう。
よくある形式では、検索対象文字列S(n文字)に検索文字列T(m文字)が含まれるかを判定します。
愚直な解法では、Sの各文字を先頭としたm文字を探索して、文字列Tと比較するO（nm）の方法が考えられます。
ゆえに、より高速なアルゴリズムを使わせたい意地悪な問題作成者は、O(nm)で間に合わないように問題を設定します。
文字列検索のアルゴリズムは１つだけではありませんが、ここは蟻本で一番最初に紹介されているローリングハッシュを解説します。

ローリングハッシュ(Rolling Hash)

ローリングハッシュは高速に文字列の検索を行うことが可能なアルゴリズムです。
結論からいえば、O(n+m)になります。

アルゴリズムの解説は蟻本（プログラミングコンテストチャレンジブック　第2版 p332-)を参考にしています。
ここではイメージを理解して、興味が出たら蟻本を読んでください（感覚でしか説明できない）。

ハッシュ要素

ローリングハッシュでは、文字列A(m文字)から、互いに素な基数bとmodの除数hを用いて以下の式でハッシュ値を求めます。

hash(A) = ( A_0*b^(m-1) + A_1*b^(m-2) + ... + A_(m-1)*b^0 ) mod h

hが十分に大きいとき文字列ごとのハッシュ値はほとんどユニークなので、
文字列s,tのハッシュ値が一致したとき、高確率でs=tである
といえます。
高速化の面では、ハッシュ値を用いることで２つの文字列の比較に各文字を比較する必要がないため、文字列の一致検証がO(n)->O(1)ですむ利点があります。

あれ？

しかしここで問題がひとつ。
m文字の文字列のハッシュ値の計算にはO(m)がかかります。
つまり、n文字の文字列におけるm文字の部分文字列のハッシュ値をすべて計算するとO(nm)です。あれ...?愚直解と変わらない？

ローリング要素

いえいえローリングハッシュはここからが本番。この式をよく眺めてみましょう。
文字列Sのすべての部分文字列についてハッシュ値を計算するとき、部分文字列s（n文字）から１文字ずらして得られる部分文字列s'のハッシュ値を

hash(s') = ( hash(s)*b - s_0*b^n + s'_(m-1) ) mod h
(s_0 = s'_(-1), s'_(m-1) = s_(m)と言い換えられます)

としても、元のハッシュ関数と同じ結果が求められるのでは？と考えます。
実際できます。イメージしてみて。
この連鎖的な生成法によって、１つの文字列についてハッシュ値の計算がO(m)->O(1),
n文字の文字列における、m文字の部分文字列の全ハッシュ値の計算がO(nm)→O(n)ですみます。

以上の工夫により、アルゴリズム全体では文字列検索の計算量はO(n+m)となります。
（s内のm文字の文字列すべてのハッシュ値計算O(n)＋tのハッシュ値計算O(m)）
速い。

イメージが掴めたらローリングハッシュの実装を見てみましょう。
注意点として、ローリングハッシュは、ハッシュ値を用いるので衝突に気をつける必要があります。

実装

ABC141 E - Who Says a Pun?
をローリングハッシュで解いてみました。
rolling_hash()関数は蟻本とほとんど同じ実装なので、理解はさほど難しくないと思います。

#include<iostream>

using namespace std;

typedef unsigned long long ull;
#define B1 100000007
#define B2 1000000007

bool rolling_hash(string const& S, int t_start, int m){
  int s_start = t_start + m;

  // B^mを用意する
  ull pow_B_m_1 = 1, pow_B_m_2 = 1;
  for(int k = 0; k < m; k++){
    pow_B_m_1 *= B1, pow_B_m_2 *= B2;
  }

  // sとtの先頭m文字のハッシュ値sh,thを計算
  ull sh1 = 0, sh2 = 0, th1 = 0, th2 = 0;
  for(int k = 0; k < m; k++){
    th1 = th1 * B1 + S[t_start + k], th2 = th2 * B2 + S[t_start + k];
    sh1 = sh1 * B1 + S[s_start + k], sh2 = sh2 * B2 + S[s_start + k];
  }

  // sをずらしてハッシュ値を更新
  for(int k = 0; s_start + k < S.length(); k++){
    if(sh1 == th1 && sh2 == th2) return true;
    if(k + s_start < S.length()){
      sh1 = sh1 * B1 + S[s_start + m + k] - S[s_start + k] * pow_B_m_1;
      sh2 = sh2 * B2 + S[s_start + m + k] - S[s_start + k] * pow_B_m_2;
    }
  }
  return false;
}

int main(){
  int n; string S;
  cin >> n >> S;

  // 一致する最大文字数を２分探索
  int ng = n+1, ok = 0, mid;
  while(ng - ok > 1){
    mid = (ng + ok) / 2;
    bool mached = false;
    // Sのi文字目をtの先頭として,t = S[i:i+mid], s = S[i+mid:]
    for(int i = 0; i < n; i++){
      if(i + mid*2 > n) break;
      if(rolling_hash(S, i, mid)){
        mached = true;
        break;
      }
    }
    if(mached) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
}

蟻本的にはこれで良いはず。多分...

実装上の工夫

今回は、ハッシュ値の衝突の回避のため、ハッシュ値生成用の基数を複数用意しました。これで衝突確率をより減らすことができます。同じ問題で同じ工夫をした方の記事を見つけたのでこちらも参考にしてみてください。
ローリングハッシュの衝突回避と定数倍高速化 peroon (id:peroon)

また、蟻本ではmodをとる代わりにunsigned long longを用いています。用いているというよりは、溢れると勝手に0に戻るだけなのですが。

終わりに

ローリングハッシュの衝突については、強い人も悩みどころらしいです。
安全で爆速なRollingHashの話 @keymoon
ローリングハッシュ自体は、基数を増やすなどの工夫で衝突確率を減らすことはできますが、ローリングハッシュ以外で安全なアルゴリズムが使えるなら（実装が間に合う場合は）そっちを採用した方が良いんじゃないかな。

ありがちな締めくくりですが、間違いがあったら教えてもらえると嬉しいです。

そういえば...蟻本片手に...？ゴリラがすぎないか？