The problem
Return every place i where text[i:i + len(pat)] == pat, in increasing order. Occurrences may overlap, and there may be very many of them.
find_every("abababac", "ababac") # [2]
find_every("aaaaa", "aa") # [0, 1, 2, 3]
find_every("abacabab", "ab") # [0, 4, 6]
Both strings have lower-case letters, and the pattern has at least one.
Limits
- The text has up to 1,000,000 letters and the pattern up to 500,000. The big tests have 4 seconds each.
- One test has 500,001 overlapping occurrences of a pattern of 500,000 letters. A loop that calls
findagain after each hit, or compares a slice at every place, does about 250 billion steps there.
Builds on STRG-2 KMP.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
11 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Overlapping places | Not run | |
| 3 | Matches that share letters | Not run | |
| 4 | A short pattern | Not run | |
| 5 | One letter | Not run | |
| 6 | Pattern longer than the text | Not run | |
| 7 | The same length | Not run | |
| 8 | No match | Not run | |
| 9 | Half a million in a row | Not run | |
| 10 | Every second place | Not run | |
| 11 | Half a million random letters | Not run |