<span>hash</span>

const ull base = 233;
ull hashsum[maxn];
ull pw[maxn];
void hash_init(string s)
{
    int len=s.size();
    pw[0] = 1;
    hashsum[0] = 1; //
    for (int i = 1; i <= len; i++)
        pw[i] = pw[i - 1] * base; //hash power
    for (int i = 1; i <= len; i++)
        hashsum[i] = hashsum[i - 1] * base + s[i - 1]; //hash: hashsum[i] <- s[i-1]
}
ull gethash(int i, int j)
{
    //i++, j++;
    return hashsum[j] - hashsum[i - 1] * pw[j - i + 1];
}