1821. Searching With a Rolling Hash
Print the 0-based position of the FIRST occurrence of the pattern p in the text
t, or -1 if it does not occur.
Occurrences may overlap each other, but only the earliest one is wanted, as a position rather than a count.
mississippi, issi -> 1 the copies at 1 and 4 overlap; 1 is earlier
aaaa, aa -> 0
xxxxabc, abc -> 4
abcdef, xyz -> -1
abc, abcd -> -1 the pattern is longer than the text
## What most people try first
Compare the pattern at every position. That is (n - m + 1) * m character
comparisons in the worst case: about 2 * 10^8 at n = 200000 and m = 1000.
The bad case is real, not theoretical: on 199990 a characters followed by
aaaaaaaaab, every window agrees with the pattern for nine characters before
failing.
## Turn each window into a number
Treat a string as a number in base B, reduced modulo a large prime M:
H(s) = (s[0] * B^(L-1) + s[1] * B^(L-2) + ... + s[L-1]) mod M
Precompute prefix values h[i+1] = (h[i] * B + t[i]) mod M and powers of B.
Then the value of the window starting at i of length m is
(h[i+m] - h[i] * pow[m]) mod M
in constant time, so every window is hashed in O(1) after O(n) setup.
## HASHES ARE NOT PROOF, SO THIS ONE VERIFIES
Two different strings can share a hash value. M is about 10^9 and there are
2 * 10^5 windows, so by the birthday argument a collision somewhere is not
astronomically unlikely, and an adversary who knows B and M can construct
one deliberately.
So this program never trusts a hash. When the window hash equals the pattern
hash it compares the m characters directly, and only then reports the
position:
for i in 0 .. n-m:
if windowHash(i) == patternHash and t[i..i+m-1] == p:
print i; stop
print -1
The answer is therefore EXACT, not probable. The hash is a filter that removes almost every window without looking at it; the correctness comes from the comparison that follows.
What the hash buys is expected time: equal hashes are rare unless the strings
really are equal, so the verification almost never runs on a non-match. Expected
cost is O(n + m), about 4 * 10^5 operations at the limits, and the worst
case is the same O(n m) as the naive scan, reached only when collisions are
manufactured.
## Cost
O(n + m) expected time, O(n + m) memory. Products reach M * B, about
1.3 * 10^11, so the arithmetic needs 64 bit integers; a 32 bit multiply
overflows here long before the answer does.
Constraints - `1 ≤ length of t ≤ 200000` - `1 ≤ length of p ≤ 200000` - both strings contain only lowercase English letters - the pattern may be longer than the text, in which case the answer is -1
Input
The first line contains the text t.
The second line contains the pattern p. Both are lowercase English letters.
Output
Print one integer on its own line: the 0-based position where the earliest occurrence of the pattern begins, or -1 if the pattern does not occur in the text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.