guest@itl:~/home/strings$
templates/hashed-deque.cpp
compilable
$cat templates/hashed-deque

Hashed Deque

Deque with O(1) rolling polynomial double hash for constant-time equality comparison.

[Strings]|
Jul 9, 2026
|explanatory_notes.md|
#hashing#deque#rolling-hash#equality
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct HashedDeque {
    static const int MAXN = 500005;
    static const ll BASE = 1000000007;
    static ll mod[2], pw[MAXN][2], inv[MAXN][2];
    static bool inited;

    deque<ll> dq;
    ll val[2] = {};
    int len = 0;

    static ll power(ll b, ll e, ll m) {
        ll r = 1; b %= m;
        while (e > 0) { if (e & 1) r = r * b % m; b = b * b % m; e >>= 1; }
        return r;
    }

    static void init() {
        if (inited) return; inited = true;
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        auto nextPrime = [](ll x) { while (true) { bool ok = x > 1; for (ll i = 2; i * i <= x && ok; i++) ok = x % i != 0; if (ok) return x; x++; } };
        mod[0] = nextPrime(900000000LL + rng() % 100000000);
        mod[1] = nextPrime(900000000LL + rng() % 100000000);
        while (mod[1] == mod[0]) mod[1] = nextPrime(900000000LL + rng() % 100000000);
        for (int j = 0; j < 2; j++) {
            pw[0][j] = inv[0][j] = 1;
            ll invB = power(BASE, mod[j] - 2, mod[j]);
            for (int i = 1; i < MAXN; i++) {
                pw[i][j] = pw[i-1][j] * BASE % mod[j];
                inv[i][j] = inv[i-1][j] * invB % mod[j];
            }
        }
    }

    HashedDeque() { init(); }

    void pushBack(ll x) {
        for (int j = 0; j < 2; j++)
            val[j] = (val[j] * BASE + x) % mod[j];
        dq.push_back(x); len++;
    }

    void pushFront(ll x) {
        for (int j = 0; j < 2; j++)
            val[j] = (x * pw[len][j] + val[j]) % mod[j];
        dq.push_front(x); len++;
    }

    void popBack() {
        ll x = dq.back(); dq.pop_back(); len--;
        for (int j = 0; j < 2; j++)
            val[j] = (val[j] - x % mod[j] + mod[j]) % mod[j] * inv[1][j] % mod[j];
    }

    void popFront() {
        ll x = dq.front(); dq.pop_front(); len--;
        for (int j = 0; j < 2; j++)
            val[j] = (val[j] - x * pw[len][j] % mod[j] + mod[j]) % mod[j];
    }

    int size() const { return len; }
    bool operator==(const HashedDeque &o) const { return len == o.len && val[0] == o.val[0] && val[1] == o.val[1]; }
};

ll HashedDeque::mod[2];
ll HashedDeque::pw[HashedDeque::MAXN][2];
ll HashedDeque::inv[HashedDeque::MAXN][2];
bool HashedDeque::inited = false;
71 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Hashed Deque

A double-ended queue that maintains a rolling polynomial hash, enabling O(1)O(1) equality comparison between two deques.

Hash Updates

For sequence a0,a1,…,an−1a_0, a_1, \dots, a_{n-1} with hash H=∑ai⋅bn−1−i mod mH = \sum a_i \cdot b^{n-1-i} \bmod m:

  • Push back (xx): H′=H⋅b+xH' = H \cdot b + x

  • Push front (xx): H′=x⋅blen+HH' = x \cdot b^{\text{len}} + H

  • Pop back (an−1a_{n-1}): H′=(H−an−1)⋅b−1H' = (H - a_{n-1}) \cdot b^{-1}

  • Pop front (a0a_0): H′=H−a0⋅blen−1H' = H - a_0 \cdot b^{\text{len}-1}

    • All operations O(1)O(1) using precomputed powers and modular inverses.

    When to Use

  • O(1)O(1) equality comparison of two sequences

  • Sliding window hashing with push/pop from both ends

  • Palindrome checking on a deque

    • Anti-Hack

    Two random prime moduli selected at runtime. Double hashing reduces collision probability.

    Complexity

  • Push / Pop — O(1)O(1)

  • Equality check — O(1)O(1)

  • Initialization — O(N)O(N) for power/inverse precomputation