Find Every Occurrence

A biologist searching a genome for a short marker needs every position where the marker starts, including copies that overlap. Write find_all(text, pattern) that returns a list of every index i where pattern starts in text, in increasing order. Overlapping occurrences all count.

Examples

find_all('abababa', 'aba')    # returns [0, 2, 4]
find_all('hello world', 'o')  # returns [4, 7]
find_all('aaaa', 'aa')        # returns [0, 1, 2]
find_all('GATTACA', 'TTT')    # returns []

Constraints

• 1 <= len(pattern) <= 100,000 and 0 <= len(text) <= 300,000
• Characters are compared exactly: upper and lower case letters are different.
• Aim for a running time that grows with len(text) + len(pattern): checking the whole pattern again at every position is far too slow for the largest inputs.