KMP String Matching Algorithm

This problem requires you to implement the Knuth-Morris-Pratt (KMP) string matching algorithm. Given two strings, a text and a pattern, your task is to find all starting indices where pattern appears in text. The algorithm must use the efficient preprocessing step by computing the longest prefix-suffix (LPS) array. In particular, the LPS array is defined as follows: for a pattern \(P[0 \ldots m-1]\), the array \(lps\) is computed so that \(lps[i]\) is the length of the longest proper prefix of \(P[0 \ldots i]\) which is also a suffix of \(P[0 \ldots i]\).

If the pattern is not present in the text, your program should output an empty result (i.e. print nothing). Your solution should read inputs from stdin and output the result to stdout.

inputFormat

The input consists of two lines: the first line contains the text string, and the second line contains the pattern string to be searched.

outputFormat

Output a single line containing the starting indices of pattern in text, separated by a single space. If the pattern is not found, output nothing.

ababcabcabababd
ababd

10