1825. How Many Pairs of Places Start the Same k Letters
Given k and a string s, count the pairs of positions (i, j) with i < j such
that the k characters starting at i are the same as the k characters
starting at j. Print the count.
The two blocks MAY OVERLAP, and a total count is wanted.
k = 2, s = aaaa -> 3 positions 0,1,2 give three pairs
k = 3, s = banana -> 1 ana at 1 and at 3, sharing a letter
k = 3, s = aabaabaab -> 5 3 + 1 + 1
k = 2, s = abcdef -> 0
k = 10, s = abcde -> 0 no block of that length exists
Read aabaabaab with k = 3. The seven windows are aab, aba, baa, aab, aba,
baa, aab. The three aab windows give three pairs, and the two aba and two
baa windows give one each, so 5 in total. A count of REPEATED BLOCKS rather
than of pairs would answer 3, which was confirmed by running it.
## What most people try first
Compare every pair of windows: O(n^2) pairs of k characters each. At
n = 200000 and k = 1000 that is 2 * 10^13 character comparisons. Even
copying each window into a dictionary costs O(n k), about 2 * 10^8
characters. The method below is O(n log n), about 3.6 * 10^6 steps.
## Group, then count inside each group
Hash every window in constant time with prefix hashes, sort the values, and for
each run of c equal values add c (c - 1) / 2.
for i in 0 .. n-k: key[i] = hash of the window at i
sort key
total = 0
for each run of length c: total = total + c * (c - 1) / 2
## Why the formula and not a nested loop inside the group
A group of c identical windows contributes one pair for every unordered pair
of its members, which is c (c - 1) / 2, because choosing two of c items can be
done in that many ways and every such choice is a valid pair. Counting instead
how many blocks repeat at all answers 3 on aabaabaab with k = 3, where the
answer is 5, since it never counts a group of three as three pairs.
Writing a nested loop inside each group is also correct and costs c^2. A
single group can hold all n - k + 1 windows, as it always does on one letter
repeated, so that version turns an O(n log n) solution back into an O(n^2)
one on exactly the input the problem is built around.
## 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 unequal 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 that any pair is falsely counted is
below 2 * 10^-8.
The answer is right with probability at least 1 - 2 * 10^-8, not with
certainty. With one modulus near 10^9 the expected number of false pairs would
be about 20, so the answer would be wrong routinely.
## Overflow
The count reaches C(200000, 2) = 19999900000, about 2 * 10^10, which is
nine times past the 2147483647 a signed 32 bit integer holds. The accumulator
must be 64 bit, and so must c * (c - 1) / 2 itself when c is 2 * 10^5. Note
that c alone, and the packed key divided down, are not the problem; the
product is.
## Cost
O(n log n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `1 ≤ k ≤ 200000` - `s` contains only lowercase English letters - the two blocks of a pair may overlap - the answer can reach about `2 * 10^10`
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: the number of pairs of positions i < j at which the two blocks of length k are equal. Print 0 if k is longer than the string.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.