1827. How Many Different Blocks of Length k
Given k and a string s, print how many DIFFERENT blocks of length exactly k
occur in s. Two occurrences of the same block count once. Print 0 if k is
longer than s.
Occurrences may overlap, and a count of DISTINCT blocks is wanted rather than a count of positions.
k = 3, s = abcabc -> 3 four windows, three different
k = 2, s = aaaa -> 1 three overlapping windows, all the same
k = 3, s = aabaabaab -> 3 seven windows, three different
k = 5, s = abababababab -> 2 eight windows, two different
k = 10, s = abcde -> 0
Problem 319 asks exactly this at k <= 1000 and |s| <= 20000, where copying
every window into a set costs O(|s| k), about 2 * 10^7 characters, and is
the intended solution. Here |s| reaches 200000 and k reaches |s|, so the
same approach copies about 10^10 characters and is not available.
## What most people try first
Cut out each window as a string and put it in a set. There are n - k + 1
windows and each costs k characters to copy and to hash, so O(n k): at
n = 200000 and k = 100000 that is about 10^10 characters, plus the memory
to hold them. The method below is O(n log n), about 3.6 * 10^6 steps, with
O(n) memory whatever k is.
## Value each window instead of copying it
Prefix hashes give the value of any window in constant time. Collect the
n - k + 1 values, sort them, and count how many times the value changes.
for i in 0 .. n-k: key[i] = hash of the window at i
sort key
answer = number of distinct values in key
The window never exists as a string at all, which is what removes the factor of
k from both the time and the memory.
## HASHING IS NOT EXACT, SO HERE IS THE PROBABILITY
TWO hashes are used, with different bases and different prime moduli near
10^9, packed into one 64 bit key. Two different windows collide under both
with probability about 1 / (M1 * M2), roughly 10^-18. There are fewer than
2 * 10^10 pairs of windows, so the chance of any collision in a whole run is
below 2 * 10^-8.
A collision would merge two genuinely different blocks and make the answer one
too small, so the result is correct with probability at least 1 - 2 * 10^-8,
not with certainty. Verifying would mean comparing the blocks, which is the
O(n k) cost the method exists to avoid. With ONE modulus near 10^9 the
expected number of collisions across 2 * 10^10 pairs is about 20, so the
answer would routinely be wrong.
## Overflow
The packed key h1 * M2 + h2 reaches about 10^18, inside the signed 64 bit
limit of 9223372036854775807. The count itself is at most 2 * 10^5 and fits
in 32 bits comfortably.
## Cost
O(n log n) time, O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `1 ≤ k ≤ 200000` - `s` contains only lowercase English letters - `k` may exceed the length of `s`
Input
The first line contains the integer k.
The second line contains the string s, of lowercase English letters.
Output
Print one integer on its own line: how many distinct strings of length exactly k occur somewhere in s. Print 0 when k exceeds the length of s.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.