Basics: prefix hashes for O(1) substring comparison

Implement class SubstringHasher, which preprocesses a string once so that any two substrings can be compared in constant time:

• SubstringHasher(s) builds the tables for s in O(len(s)).
• get(l, r) returns the polynomial hash of s[l:r] (0 <= l <= r <= len(s)), defined exactly as below.
• same(i, j, length) returns True if s[i:i+length] == s[j:j+length]. Both ranges are guaranteed to fit inside s, and length may be 0.

h = SubstringHasher("abcabd")
h.same(0, 3, 2)    # True   ("ab" == "ab")
h.same(0, 3, 3)    # False  ("abc" != "abd")
h.get(0, 2) == h.get(3, 5)   # True

The hash of a string t treats its characters as digits in base B = 131 modulo the prime M = 2**61 - 1 (both given in the starter), first character most significant:

hash(t) = (ord(t[0]) * B**(k-1) + ord(t[1]) * B**(k-2) + ... + ord(t[k-1])) % M,   k = len(t)

The empty string hashes to 0. The tests check get against this exact value.

In Python, B and M are given in the starter. In C++ or Java, declare them yourself, and note that the product of two values below 2**61 overflows 64 bits: multiply through __uint128_t in C++ ((unsigned long long)((__uint128_t) a * b % M)), or in Java combine Math.multiplyHigh(a, b) with a * b to reduce the 122-bit product modulo M (since 2**61 ≡ 1 (mod M), the high part just gets added back in).

Store prefix hashes h[i] (the hash of s[:i]) and powers p[i] = B**i % M, so get and same never look at the characters. The tests build a hasher for a 200,000-character string and make 100,000 calls on substrings tens of thousands of characters long; a Python loop over the characters is far too slow.