Pattern Indices Finder

Given two strings S and P, your task is to find and output all starting indices of occurrences of P in S using case-sensitive matching.

You are expected to implement a solution that runs efficiently for long strings. A recommended method is the Knuth-Morris-Pratt (KMP) algorithm whose prefix function is given by $$lps[i]=\max\{k : 0\le k<i \text{ and } S[0..k-1]=S[i-k..i-1]\}.$$

If no occurrence is found, output an empty line.

inputFormat

The input consists of two lines from standard input:

• The first line contains the string S.
• The second line contains the pattern string P to search for in S.

outputFormat

Output a single line to standard output containing the starting indices (0-indexed) of all occurrences of P in S, separated by a single space. If there are no occurrences, output an empty line.

abracadabra
abra

0 7