Rabin-Karp String Matching
Implement the Rabin-Karp algorithm to find all occurrences of a pattern in a text using rolling hash.
Input format
The first line contains the text. The second line contains the pattern (lowercase, |pat| ≤ |text| ≤ 40).
Output format
Print 0-based occurrence indices space-separated, or -1 if none. Half cases have matches.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
kgaedgaedokgaedgaed gaedExpected output
1 5 11 15Example 2
Input
lnjutlnlnwiblnlnln lnExpected output
0 5 7 12 14 16