Expert · String algorithms · 249 of 264
Find every match
Print every position (from 0) where the pattern occurs in the text, overlapping matches included. Texts have up to 9000 characters: try an efficient method such as KMP rather than comparing at every position.
Input: the text, then the pattern. Output: the positions on one line, or none
Examples
Input
abababa aba
Output
0 2 4
Input
hello z
Output
none
Input
aaaa aa
Output
0 1 2
One more test checks other inputs when you press Check.
Stuck? The idea behind string algorithms
Finding patterns in text: compare a window of the text with the pattern as it slides along, or use what has already matched to skip ahead.
str.find(pattern, start) gives the next position, or -1 when there is none.
text, pat = "abababa", "aba"
i = text.find(pat)
while i != -1:
print(i)
i = text.find(pat, i + 1)Watch for: Matches can overlap ("aba" twice in "ababa"): move on by one, not by the pattern's length.