901. Pattern Hits
A librarian scans a long scroll of symbols, text, looking for every place where a stamp sequence, pattern, shows up. Occurrences may overlap: in zzzz the sequence zz appears three times.
Return an array with the starting index (0-based) of every occurrence of pattern inside text, in increasing order. Return an empty array if there is none, or if pattern is longer than text.
Aim for time O(n + m) where n and m are the two lengths, and O(m) extra space; comparing the pattern against every start position is too slow.
Example 1
- Input:
- text = "tulipsandtulipstulip", pattern = "tulips"
- Output:
- [0,9]
- Explanation:
The pattern starts at index 0 and again at index 9.
Example 2
- Input:
- text = "zzzzzz", pattern = "zzz"
- Output:
- [0,1,2,3]
- Explanation:
Overlapping hits count: the pattern starts at indices 0, 1, 2 and 3.
Example 3
- Input:
- text = "harbour", pattern = "dock"
- Output:
- []
- Explanation:
The pattern never occurs, so the result is empty.
Constraints
1 ≤ pattern.length ≤ 105
1 ≤ text.length ≤ 105
Both strings contain only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n+m)
- Space
- O(m)