Overlapping occurrences
Input
find_all("aaaa", "aa")
Output
[0, 1, 2]
Overlapping matches are included: 'aa' at positions 0,1,2.
Full lesson preview
Find all occurrences of a substring
Return all starting indices where a substring appears in a string (allowing overlapping matches).
Python practice15 minString PatternsIntermediateLast updated March 18, 2026
Problem statement
Write a function find_all(s, sub) that returns a list of all starting indices where the substring sub occurs inside s. Matches should be case-sensitive and overlapping matches must be included. If sub is an empty string, return an empty list.
Examples:
- find_all('ababab','aba') -> [0,2]
- find_all('aaaa','aa') -> [0,1,2]
Return the indices in ascending order.
Task
Implement a find_all(s, sub) function that returns a list of all start indices (0-based) of sub in s, including overlapping occurrences.
Examples
Input format
Two strings: s (haystack) and sub (needle) passed as find_all(s, sub).
Output format
Return a list of integer indices for each match start position.
Constraints
- 0 <= len(s) <= 5000
- 0 <= len(sub) <= 5000
- If sub is empty, return an empty list
- Use an algorithm that is efficient enough for the constraints above
Samples
Sample 1
Input
find_all("abracadabra", "abra")
Output
[0, 7]
Two non-overlapping occurrences at positions 0 and 7.