The Highlight Reel
You are building EA Sports' match replay system. After every game, the system records a sequence of match events as a string. The highlight detector needs to find every occurrence of a specific play sequence (pattern) within the full match log (text).
Given a match event log text and a highlight pattern, return a sorted list of all starting indices (0-based) where the pattern occurs in the text. Return an empty list if the pattern never appears.
Your solution must run in O(n + m) time — the naive O(n×m) approach will time out on large match logs.
Example 1
("abracadabraabracadabra", "abra")[0, 7, 11, 18]The highlight sequence abra appears at positions 0, 7, 11, and 18 in the match log.
Example 2
("aaaaaaa", "aaa")[0, 1, 2, 3, 4]Overlapping matches — after finding aaa at index 0, KMP uses the LPS array to find the next match at index 1, not index 3.
Example 3
("abacabadabacabaeabacabadabacabaf", "abacabadabacaba")[0, 16]Complex repeating prefix pattern. The LPS array enables efficient sliding without missing the second occurrence at index 16.
- ›1 <= len(text) <= 10^6
- ›1 <= len(pattern) <= 10^4
- ›Both strings consist of lowercase English letters only
Loading question…