Как сравнить две произвольные подстроки за O(1) после препроцессинга хешей?

Считаем префиксные хеши H[i] = Σ_{k<i} s[k] * base^k mod M и заранее степени pw[i] = base^i. Тогда хеш подстроки s[l..r] (включительно) получается как (H[r+1] - H[l]) * base^{-l}, но чтобы не считать обратный элемент, обычно домножают на pw при сравнении.

struct Hashing {
    vector<uint64_t> H, pw;
    Hashing(const string& s, uint64_t base) {
        int n = s.size();
        H.assign(n + 1, 0); pw.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            H[i+1] = mulmod(H[i], base);
            H[i+1] = (H[i+1] + s[i]) % M;     // схема Горнера: старший разряд слева
            pw[i+1] = mulmod(pw[i], base);
        }
    }
    uint64_t get(int l, int r) {                  // хеш s[l..r]
        uint64_t res = (H[r+1] + M - mulmod(H[l], pw[r-l+1])) % M;
        return res;
    }
};

Здесь я взял схему Горнера (старший коэффициент — у первого символа), поэтому при «вырезании» префикса его домножают на pw[длина подстроки]. Сравнение get(l1,r1) == get(l2,r2) — O(1), препроцессинг — O(n).