1823. The First Block of Length k That Has Appeared Before
Given k and a string s, print the smallest position j such that the block
s[j..j+k-1] is equal to s[i..i+k-1] for some i < j. Print -1 if no block
of length k ever repeats.
The two copies MAY OVERLAP, and a single position is wanted.
k = 2, s = aaaa -> 1 the block at 1 repeats the one at 0
k = 3, s = banana -> 3 ana at 1 and again at 3, sharing one letter
k = 6, s = aabaabaab -> 3 aabaab at 0 and at 3, sharing three letters
k = 2, s = abcdef -> -1
k = 9, s = aabaabaab -> -1 only one block of that length exists
Requiring the two copies to be disjoint changes every one of the first three
answers: aaaa would give 2, and aabaabaab with k = 6 would give -1. That
version was run to confirm it.
## What most people try first
Compare every block with every earlier block: O(n^2) pairs, each costing k
characters, so O(n^2 k). At n = 200000 and k = 1000 that is far past
10^13. Even storing every block in a set costs O(n k) characters of copying
and hashing, about 2 * 10^8 at those limits. The method below is O(n log n),
about 3.6 * 10^6 steps.
## Value every block in constant time
Build prefix hashes as in problem 1821, so the block at i has a value in
O(1). Then sweep positions upwards, remembering every value already seen, and
stop at the first position whose value has been seen before.
seen = empty set
for j in 0 .. n-k:
v = hash of the block at j
if v is in seen: print j; stop
add v to seen
print -1
Without a hash set, pair each value with its position, sort the pairs, and inside each run of equal values take the SECOND smallest position; the answer is the smallest of those over all runs.
## Why the second smallest position and not the first
The question asks for the first position that REPEATS something earlier. Within
a group of identical blocks sitting at positions i1 < i2 < ..., the first one
repeats nothing; i2 is the earliest that does. Taking i1 would report the
original rather than the repeat.
## HASHING IS NOT EXACT, SO HERE IS THE PROBABILITY
This problem uses TWO independent hashes, with different bases and different
prime moduli near 10^9, packed into one 64 bit key. Two different blocks
collide under both at once with probability about 1 / (M1 * M2), about
10^-18. There are fewer than 2 * 10^5 blocks, so fewer than 2 * 10^10
pairs, and the chance that any pair collides in a whole run is below
2 * 10^-8.
The answer is therefore correct with probability at least 1 - 2 * 10^-8, not
with certainty. With ONE modulus near 10^9 the same argument gives about
2 * 10^10 / 10^9 = 20, which is not a probability at all: a collision would be
expected, not unlikely. That is the whole reason for the second hash.
## Overflow
The packed key is h1 * M2 + h2, at most about 10^18, which fits in a signed
64 bit integer whose limit is 9223372036854775807. The intermediate products
inside the hashing also reach about 10^18.
## Cost
O(n log n) for the sort, 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`, in which case the answer is -1 - the two equal blocks may overlap
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 smallest position at which a block of length k begins that is equal to a block of length k beginning at some earlier position, or -1 if no block of length k repeats.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.