Substring Search
Given a long text
t and a string s, you are asked to find all the occurrences of s in the text t. You are asked to find the starting positions in t that match s.Input
The first line of the input contains the text
t (1 ≤ |t| ≤ ).The second line of the input contains the string
s (1 ≤ |s| ≤ |t|).Output
For each occurrence of
s in t, output the starting position in t where it occurs. The positions should be in ascending order (from the beginning of the text to the end) separated by a space. The indexing starts from 0.Examples
Input | Output |
habababohabo
ba | 2 4 |
barfoobarfoobarfoobarfoobarfoo
foobarfoo | 3 9 15 21 |
Explanation
- habababohabo → ha
bababohabo, habababohabo
- barfoobarfoobarfoobarfoobarfoo → bar
foobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB