Every Word, Back to Back

words is a list of words that all have the same length, and the list may hold the same word more than once. Write find_runs(text, words) that returns every index i where a run of all the words starts in text: the part of text starting at i is made of every word in words, each used exactly as many times as it appears in the list, joined together in any order with nothing in between.

Return the indexes as a list sorted from smallest to largest.

Examples

find_runs('catdogxcatdogcat', ['cat', 'dog'])   # returns [0, 7, 10]
find_runs('onetwoone', ['one', 'two'])          # returns [0, 3]
find_runs('aaaa', ['aa', 'aa'])                 # returns [0]
find_runs('redbluered', ['red', 'red'])         # returns []

In the first example 'catdog' starts at index 0 and at index 7, and 'dogcat' starts at index 10. In the last example 'red' appears twice, but never twice in a row.

Constraints

• 1 <= len(words) <= 5,000
• 1 <= len(words[i]) <= 30, and all the words have the same length
• 0 <= len(text) <= 100,000
• text and the words hold lowercase letters and digits

Note

Checking every index against all the words is too slow when there are thousands of them.