Every Pattern Occurrence
MediumTries & Strings
Problem
A log scanner looks for a signature pattern inside a long text. Return every index where an occurrence of pattern starts, in increasing order. Occurrences may overlap.
If the pattern never occurs, return an empty array.
Example 1
- Input:
- text = "abababa", pattern = "aba"
- Output:
- [0, 2, 4]
The three occurrences overlap by one letter each.
Example 2
- Input:
- text = "mississippi", pattern = "issi"
- Output:
- [1, 4]
Example 3
- Input:
- text = "abc", pattern = "d"
- Output:
- []
Constraints
- 1 ≤ pattern.length ≤ 10^5
- 1 ≤ text.length ≤ 10^6
- Lowercase English letters only.
Hint
Show the first hint
The naive scan restarts from scratch after a mismatch. What does it already know at that moment?
Walkthrough
How to approach it
01Clarify before coding
- Can occurrences overlap? Yes: "aa" occurs four times in "aaaaa".
- Can the pattern be longer than the text? Yes; return [].
- Is the output 0-based? Yes, start indices in increasing order.
02Brute force
Try every start index and compare the pattern character by character.
Cost: O(n·m): with text a^n and pattern a^(m-1)b that is about 5·10^4 · 5·10^4 = 2.5·10^9 comparisons.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.