A newsroom's ticker tape is one long string. The editors hand you a batch of phrases, all the same length k, and want to know how many times each one appears on the tape. Occurrences may overlap: "aa" appears 3 times in "aaaa".
Write count_phrases(tape: str, phrases: list[str]) -> list[int] that returns the counts in the same order as phrases.
count_phrases("abababa", ["aba", "bab", "abb"]) # [3, 2, 0]
count_phrases("aaaa", ["aa", "aa"]) # [3, 3] (the same phrase can be asked twice)
count_phrases("hi", ["hello"]) # [0] (longer than the tape)
1 <= len(tape) <= 200,000,0 <= len(phrases) <= 50, every phrase has the same lengthk >= 1, and the phrases' total length is at most 200,000. Any characters may appear.kcan be tens of thousands, so slicing out every window (tape[i:i+k]for eachi) copies O(n·k) characters and is far too slow; so is comparing each phrase at every position.
Aim for about O(len(tape) + total phrase length).
Show hint
Give every length-k window of the tape a fingerprint you can update in O(1) as the window slides one step (a polynomial hash such as B = 131, M = 2**61 - 1, as in the Basics drill; the Python starter defines both; in C++ or Java, a pair of moduli near 10^9 avoids 128-bit products), count the fingerprints in a dict, then fingerprint each phrase and look it up.