1828. The Blocks of Length k Both Words Contain
Given k and two words s and t, print how many DIFFERENT strings of length
exactly k occur in both of them.
k = 2, s = abcab, t = bcabd -> 3 ab, bc, ca; bd is only in t
k = 2, s = aaaa, t = aaa -> 1 every window of both is aa
k = 5, s = banana, t = ananas -> 1 anana
k = 3, s = abc, t = xyz -> 0
k = 4, s = abc, t = abcd -> 0 the first word is too short
Occurrences may overlap inside either word, and a count of DISTINCT shared
blocks is wanted. A block occurring five times in s and twice in t counts
once.
## What most people try first
Build the set of windows of each word as actual strings and intersect them. Each
window costs k characters to copy and hash, so it is O((|s| + |t|) k): about
2 * 10^10 characters at 200000 each with k = 50000. The method below is
O((|s| + |t|) log), about 7 * 10^6 steps.
## Value the windows, then intersect the numbers
A = the distinct hashes of the length-k windows of s
B = the distinct hashes of the length-k windows of t
answer = |A intersect B|
Sort both lists of values, remove duplicates in each, and walk the two sorted
lists together counting matches. Deduplicating BEFORE the walk is what makes the
answer a count of distinct blocks rather than of pairs of positions: aaaa
against aaa has three windows on one side and two on the other, six position
pairs, and exactly one shared block.
## The length check that comes first
If k exceeds either word, that word has no window at all and the answer is 0.
Computing n - k + 1 without the check gives a negative count, which in most
languages becomes a loop that never runs, and in C a very large unsigned one.
## 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 blocks collide under both with
probability about 10^-18. There are fewer than 4 * 10^10 cross pairs, so the
chance that any false match is counted is below 4 * 10^-8.
The answer is right with probability at least 1 - 4 * 10^-8, not with
certainty. No verification is done, because comparing a matched pair costs k
characters and there can be 2 * 10^5 matches, which restores the cost the
method removed.
## Overflow
The packed key reaches about 10^18, needing 64 bits against the signed limit
of 9223372036854775807. The answer itself is at most 2 * 10^5.
## Cost
O((|s| + |t|) log) time and O(|s| + |t|) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `1 ≤ length of t ≤ 200000` - `1 ≤ k ≤ 200000` - both words contain only lowercase English letters - a block occurring several times in a word still counts once
Input
The first line contains the integer k.
The second line contains the word s.
The third line contains the word t. Both words are lowercase English letters.
Output
Print one integer on its own line: how many distinct strings of length exactly k occur in both words. Print 0 if k is longer than either word.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.