KMP Algorithm (LPS Array)
Implement the Knuth-Morris-Pratt algorithm using the longest prefix-suffix array for pattern matching.
Input format
The first line contains the text. The second line contains the pattern (lowercase).
Output format
Print two lines: line 1 the LPS array of the pattern (space-separated); line 2 the occurrence indices or -1.
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
ceqhsdceqhsdceqhsdcgcsxyg ceqhsdExpected output
0 0 0 0 0 0
0 6 12Example 2
Input
xtjefmtlzygu xtjefmtlExpected output
0 0 0 0 0 0 0 0
0