структура хэшей

using namespace std;

const int N = 1000009;

struct Hash
{
    int h1, h2;

    Hash(int x, int y) : h1(x), h2(y) {}
    Hash(int x) : h1(x), h2(x) {}
    Hash() : h1(0), h2(0) {}
};

const Hash P = { 31, 37 }, MOD = { (int)1e9 + 7, (int)1e9 + 9 };

vector<Hash> pw(N);

Hash operator + (Hash a, Hash b)
{
    return { (a.h1 + b.h1) % MOD.h1, (a.h2 + b.h2) % MOD.h2 };
}

Hash operator - (Hash a, Hash b)
{
    return { (a.h1 - b.h1 + MOD.h1) % MOD.h1, (a.h2 - b.h2 + MOD.h2) % MOD.h2 };
}

Hash operator * (Hash a, Hash b)
{
    return { (a.h1 * b.h1) % MOD.h1, (a.h2 * b.h2) % MOD.h2 };
}

Hash operator % (Hash a, Hash b)
{
    return { a.h1 % b.h1, a.h2 % b.h2 };
}

Hash operator * (Hash a, int b)
{
    return { (a.h1 * b) % MOD.h1, (a.h2 * b) % MOD.h2 };
}

bool operator != (Hash a, Hash b)
{
    return a.h1 != b.h1 || a.h2 != b.h2;
}

bool operator == (Hash a, Hash b)
{
    return a.h1 == b.h1 && a.h2 == b.h2;
}

void build_powers()
{
    pw[0] = 1;

    for (int i = 1; i < N; i++)
    {
        pw[i] = pw[i - 1] * P;
    }

    return;
}

vector<Hash> build_hash(string s)
{
    vector<Hash> hs((int)s.size());
    hs[0] = 0;

    for (int i = 1; i < (int)s.size(); i++)
    {
        hs[i] = hs[i - 1] + pw[i] * s[i];
    }

    return hs;
}

Hash get_hash(vector<Hash>& hs, int l, int r)
{
    return hs[r] - hs[l - 1];
}