Find Pattern Occurrences

You are given a text string and a pattern string. Your task is to find all starting indices where the pattern occurs in the text. To solve this problem efficiently, you are encouraged to implement the Knuth-Morris-Pratt (KMP) algorithm.

The KMP algorithm preprocesses the pattern string to compute the longest proper prefix which is also a suffix (LPS) array. The formula for updating the LPS array is given by: \( LPS[i] = \max\{k: k < i \text{ and } pattern[0..k-1] = pattern[i-k+1..i]\} \). This preprocessing allows the search to skip characters intelligently without re-examining previously matched characters.

Input and Output: Your program should read from standard input. The first line will contain the text string, and the second line will contain the pattern string. Output the starting indices (0-indexed) of all occurrences of the pattern in the text on one line, separated by a space. If the pattern does not occur, output an empty line.

inputFormat

The input consists of two lines:

• The first line contains the string text in which to search.
• The second line contains the pattern to search for.

outputFormat

Output a single line containing the 0-indexed starting positions of each occurrence of the pattern in the text, separated by a single space. If no occurrences are found, output an empty line.

## sample

abracadabra
abra

0 7

</p>