Rolling Hash Structure

Problem

Precompute polynomial hashes so any substring hash can be answered in O(1).

s is the string, base and mod define the polynomial hash with characters weighted by growing powers, and queries is a list of [l, r] pairs (0-based, inclusive). Use prefix hashes and powers of base to extract each substring value.

Return the list of substring hashes.

Hint

Subtract the shifted prefix hash of the previous position, then take the result modulo the field.

Test cases

case 1

in: ["abcd",31,1000000007,[[0,0],[0,3],[1,2]]]

expected: [97,2987074,3137]

case 2

in: ["a",131,97,[[0,0]]]

expected: [0]

case 3

in: ["",31,1000000007,[]]

expected: []

case 4

in: ["hello",131,1000000007,[[0,4],[1,3]]]

expected: [856916412,1747517]

Starter codePython

def rolling_hash_queries(s, base, mod, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor