Polynomial Rolling Hash

A polynomial rolling hash summarizes a string with modular arithmetic so that substring fingerprints can be extracted quickly. Unlike the previous fixed-window search, this lesson preprocesses the entire string once and answers arbitrary interval-comparison queries. We store two modular hashes to make accidental collisions less likely. Equal double hashes are still probabilistic evidence, not an exact equality proof. The example deliberately prints POSSIBLY EQUAL for equal fingerprints and DIFFERENT for a definite mismatch.

Prerequisites: Rabin–Karp basics, modular arithmetic, prefix arrays, and half-open string intervals.

Build the idea

1. 1. Choose one consistent polynomial orientation. We use the left-to-right recurrence H[i+1]=(H[i]·B+value(s[i])) mod Q, with H[0]=0. Thus prefix ab has aB+b, and prefix abc has aB²+bB+c. Other implementations use increasing powers from left to right; both conventions work, but their substring formulas are different. Mixing formulas from the two conventions is a common source of incorrect results. Characters are unsigned byte values plus one, and indices are 0-based.
2. 2. Precompute prefixes and powers together. Store power[0]=1 and power[i+1]=power[i]·B mod Q for every length through N. Store every prefix hash H[i]. Each next entry depends only on the preceding entry, so the complete preprocessing scans the string once. For abcde, H[5] contains contributions from all five characters. H[2] contains the contribution of ab with powers appropriate to a two-character prefix. To remove it from H[5], shift it by the length of the suffix being retained.
3. 3. Derive the half-open substring formula. For interval [l,r), compute H[r]−H[l]·power[r−l] modulo Q. The shifted prefix subtraction removes exactly the terms belonging to indices before l. What remains has the same polynomial form as hashing s[l..r) from scratch, independent of its original position. For abcde and [2,5), the result is cB²+dB+e. No modular inverse is needed with this orientation. An empty interval has length zero and hash H[l]−H[l]=0.
4. 4. Compare length before fingerprints. Two equal strings must have equal lengths. Only after that check do we compare their two hashes. In banana, intervals [1,4) and [3,6) both contain ana and get matching fingerprints. Intervals [0,3) and [2,5) contain ban and nan, so a mismatch proves DIFFERENT. Intervals [2,2) and [4,4) are both empty. The example prints POSSIBLY EQUAL when both length and fingerprints agree, including those empty intervals. It never silently upgrades a hash match into certainty.
5. 5. Understand what double hashing guarantees. We use moduli 1,000,000,007 and 1,000,000,009 and base 911,382,323. Arithmetic remains within signed long long for these constants. Unequal strings may collide under either modulus, and could collide under both. The fixed parameters in this educational program do not justify a universal numerical collision probability for adversarial input. Randomizing a suitable base can reduce predictable attacks, but still does not prove equality. When exactness is required, verify the actual substrings after a hash match or use an exact string algorithm.
6. 6. Separate the data structure from its applications. The Hash struct owns its prefix/power arrays and exposes get(l,r). It can be built for several strings using the same base and moduli, allowing cross-string comparisons after checking lengths. Binary search on the common-prefix length plus hash checks gives a fast probabilistic longest-common-prefix query. Comparing a string to its reversed version can filter palindrome candidates. Grouping substrings by hash needs their lengths and a collision policy; a map of hash values alone does not certify that all members are identical.
7. 7. Respect the static preprocessing contract. These prefix arrays describe the string at construction time. Changing one character invalidates later prefixes, so this simple implementation is not an O(1)-update dynamic structure. Dynamic hashing can use Fenwick or segment trees with compatible power normalization. The program validates every interval with 0≤l≤r≤N and prints INVALID for malformed queries rather than reading outside the arrays. getline allows spaces and the empty string; the query count follows on the next line.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<utility>
using namespace std;
struct Hash{
    static constexpr long long B=911382323;
    static constexpr long long M1=1000000007,M2=1000000009;
    vector<long long>h1,h2,p1,p2;
    Hash(const string&s):h1(s.size()+1),h2(s.size()+1),p1(s.size()+1,1),p2(s.size()+1,1){
        for(int i=0;i<(int)s.size();i++){
            int x=(unsigned char)s[i]+1;
            // Prefixes use descending powers; store both moduli consistently.
            h1[i+1]=(h1[i]*B+x)%M1;
            h2[i+1]=(h2[i]*B+x)%M2;
            p1[i+1]=p1[i]*B%M1;
            p2[i+1]=p2[i]*B%M2;
        }
    }
    pair<long long,long long>get(int l,int r)const{
        // Remove the shifted preceding prefix; interval [l,r) is half-open.
        return {(h1[r]-h1[l]*p1[r-l]%M1+M1)%M1,(h2[r]-h2[l]*p2[r-l]%M2+M2)%M2};
    }
};
int main(){
    string s;
    getline(cin,s);
    Hash hash(s);
    int q;
    cin>>q;
    int n=(int)s.size();
    auto valid=[&](int l,int r){
        return 0<=l&&l<=r&&r<=n;
    };
    while(q--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(!valid(a,b)||!valid(c,d)){
            cout<<"INVALID\n";
            continue;
        }
        // Hash equality remains probabilistic; a mismatch proves inequality.
        if(b-a==d-c&&hash.get(a,b)==hash.get(c,d)){
            cout<<"POSSIBLY EQUAL\n";
        }
        else{
            cout<<"DIFFERENT\n";
        }
    }
}

Complexity analysis

O(N) preprocessing time and O(N) space for four arrays. Extracting one substring fingerprint and comparing two fingerprints each take O(1). Q queries take O(Q) after preprocessing. Exact verification adds O(L) per hash-equal comparison of length L; prefix hashes do not make that verification constant-time.

Example input and output

First line is a string. Then Q, followed by Q lines l1 r1 l2 r2, using half-open intervals. Output POSSIBLY EQUAL, DIFFERENT, or INVALID.

Input

banana
3
1 4 3 6
0 3 2 5
2 2 4 4

Output

POSSIBLY EQUAL
DIFFERENT
POSSIBLY EQUAL

Both ana intervals match; ban and nan differ; the final pair consists of two empty substrings.

Practical applications

Substring-comparison filters, probabilistic longest-common-prefix queries, repeated-substring grouping, and palindrome candidate checks. Exact alternatives include suffix arrays/LCP, KMP, Z, and Manacher for palindromes.

Check your understanding

Why multiply H[l] by B^(r−l) before subtracting it from H[r]?

Put it into practice

Build hashes for a second string and support cross-string interval comparisons.