Strings

Hash

template < int N >
struct StringHashing {
  char s[N];
  i64 mod[2] = {1610612741ll, 805306457ll};
  i64 pw[N][2];
  i64 w[N][2];
  void init (int m) {
    pw[0][0] = pw[0][1] = 1;
    for (int i = 1;i <= m; ++ i) {
      pw[i][0] = pw[i - 1][0] * 233ll % mod[0];
      pw[i][1] = pw[i - 1][1] * 233ll % mod[1];
    }
    w[0][0] = w[0][1] = 0;
    for (int i = 1;i <= m; ++ i) {
      i64 Z = (i64) s[i];
      w[i][0] = (w[i - 1][0] * 233ll + Z) % mod[0];
      w[i][1] = (w[i - 1][1] * 233ll + Z) % mod[1];
    }
    return ;
  }
  i64 query (int l, int r, int v) {return (w[r][v] + mod[v] - (w[l - 1][v] * pw[r - l + 1][v] % mod[v])) % mod[v];}
  std :: pair < i64, i64 > val (int l, int r) {return std :: make_pair (query (l, r, 0), query (l, r, 1));}
};