Write find_all(text, pattern) -> list[int]: every start index i with text[i:i + len(pattern)] == pattern, in increasing order. Occurrences may overlap. Return [] if the pattern is empty or longer than the text.
find_all("abracadabra", "abra") # [0, 7]
find_all("aaaa", "aa") # [0, 1, 2] overlapping matches all count
find_all("ab", "abc") # []
Constraints: 0 <= len(pattern), len(text) <= 300_000, any characters.
Comparing the pattern at every position is O(n·m), hopeless when both strings are long: one test has a 300k-character text and a 150k-character pattern, another has 150,001 overlapping matches of a 150k-character pattern, so even confirming each match character by character is too slow. Aim for O(n + m).
Show hint
Give the pattern and each same-length window of the text a numeric fingerprint (a polynomial hash), updating the window's value in O(1) as it slides one character. With a modulus as large as 2**61 - 1 and a large base, equal fingerprints can be trusted.