KMP Pattern Search

This problem requires you to implement the Knuth–Morris–Pratt (KMP) algorithm for pattern matching. You need to compute the Longest Prefix Suffix (LPS) array for a given pattern and then use it to search for all occurrences of the pattern in a text.

For a pattern \(P[0\dots m-1]\), the LPS array is defined such that \(\mathrm{LPS}[i]\) is the length of the longest proper prefix of \(P[0\dots i]\) which is also a suffix of \(P[0\dots i]\). Formally, it satisfies:

\[ \mathrm{LPS}[i] = \max\{ k : k < i+1 \text{ and } P[0 \dots k-1] = P[i-k+1 \dots i] \} \]

Once the LPS is computed, the KMP algorithm uses it to efficiently search for the pattern in the given text. Your program should take the text and the pattern as input (each provided in a separate line) and output the starting indices of all occurrences of the pattern in the text, separated by a single space.

inputFormat

The first line of the input contains the text string. The second line contains the pattern string to search for.

outputFormat

Output a single line containing the starting indices (0-indexed) of all occurrences of the pattern in the text separated by a space. If the pattern does not occur in the text, output an empty line.

ABABDABACDABABCABAB
ABABCABAB

10