Longest Prefix-Suffix Array

Given a string S, compute an array where the i-th element represents the length of the longest proper prefix of the substring S[0...i] which is also a suffix of that substring.

A proper prefix is a prefix of the string that is not equal to the string itself. This array is commonly known as the LPS (Longest Proper Prefix which is also Suffix) array used in the Knuth-Morris-Pratt (KMP) algorithm.

Example: For S = ababaca, the LPS array is [0, 0, 1, 2, 3, 0, 1].

inputFormat

The input consists of a single line containing the string S. The string may be empty.

outputFormat

Output the LPS array for the given string. The elements must be printed in order and separated by a single space. If the string is empty, print an empty line.

ababaca

0 0 1 2 3 0 1