For fast search-and-highlight, Meherun's tool needs every occurrence of a search pattern inside a huge document, computed efficiently rather than scanning character by character. Given a text T and pattern P, find every starting index (0-indexed) in T where P occurs as a substring. Use the Z-function or KMP algorithm for O(|T|+|P|), not naive O(|T|*|P|).
Input
Two strings T and P on two lines.
Output
All starting indices where P occurs in T, space-separated (empty line if none).
Constraints
1 ≤ |P| ≤ |T| ≤ 10^6
Sample Input
ababcabab ab
Sample Output
0 2 5 7
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.