A log analyser needs every place a short pattern appears inside a long text. Return the list of all starting indices, in increasing order, at which pattern occurs in text. Occurrences may overlap.
Examples
Input: text = "abababa", pattern = "aba"
Output: [0, 2, 4]
Input: text = "hello", pattern = "z"
Output: []
Constraints
0 <= len(text) <= 10**5,1 <= len(pattern) <= 10**4- Target: O(len(text) + len(pattern)) time. A naive scan is O(n * m) and too slow for adversarial inputs.
Goals
- Build the failure (longest proper prefix-suffix) table of the pattern
- Scan the text once, never moving backwards
- Report overlapping matches