Rolling Hash

// ある文字列をHash値に置き換え同等かの比較に使用できる。
// rolling_hash(s)としておくとO(N)でハッシュ値を構築する。
// 文字列の区間を指定してやるだけでハッシュ値を得ることができる。
// なおハッシュ値は素数で割った余りとしているので衝突の可能性がある。
// よって、素数を2つ使った比較により衝突の可能性を下げている。

long long mod[2] = {1000000007,1000000009};
ll hs[2][5100], pw[2][5100];

void rolling_hash(string &s){
  ll base = 257;
  memset(hs,0,sizeof(hs));
  memset(pw,0,sizeof(pw));
  rep(i,0,2){
    pw[i][0] = 1;
    hs[i][0] = 0;
    rep(j,0,s.sz){
      pw[i][j+1] = pw[i][j]*base%mod[i];
      hs[i][j+1] = (hs[i][j]*base+s[j])%mod[i];
    }
  }
}

long long hash_(ll l, ll r, ll i){
  return (hs[i][r+1]-(hs[i][l]*pw[i][r-l+1])%mod[i]+mod[i])%mod[i];
}

ll match(ll l1, ll r1, ll l2, ll r2) {
  ll ret = 1;
  rep(i,0,2){
    ret &= hash_(l1,r1,i)==hash_(l2,r2,i);
  }
  return ret;
}