1845. The Shortest Block Behind Each Prefix
For every k from 1 to n, print the smallest period of the prefix s[0..k-1].
A number p is a period of a string of length k when every character equals the
one p places later, as far as the string runs.
aabaabaab -> 1 1 3 3 3 3 3 3 3
aaaa -> 1 1 1 1
abcdef -> 1 2 3 4 5 6
abcabcabc -> 1 2 3 3 3 3 3 3 3
aab -> 1 1 3
Problem 1806 asks this for the whole string only. Here every prefix is wanted,
and the sequence is not monotone in any simple way: aab goes 1, 1, 3, losing
its short period entirely at the third character.
The period need not divide the length. aabaabaab has period 3 at every prefix
from the third onwards, including the prefixes of length 4, 5, 7 and 8.
## What most people try first
For each prefix, test candidate periods 1, 2, 3, ... until one works. Testing
p on a prefix of length k costs k - p, so a single prefix can cost
k^2 / 2 and the whole array costs O(n^3) in the worst case. Even the
optimistic reading, one successful test per prefix, is O(n^2), which is
4 * 10^10 at n = 200000. The method below is O(n), about 4 * 10^5.
## The prefix function answers all of them at once
answer for k = k - pi[k-1]
## Why the same formula works at every prefix
Problem 1806 argues that a period p of a string of length k corresponds
exactly to a border of length k - p, and that the smallest period corresponds
to the longest border.
That argument was about a whole string, and pi[k-1] IS the longest border of
the whole string s[0..k-1]. So the identical reasoning applies to every
prefix, with no extra work: the array that answers one question answers n of
them.
That is the point of this problem. The prefix function is often presented as scratch state for a search, and it is really a table of answers about every prefix at once.
## The boundary
k = 1. pi[0] is 0, so the period is 1, which is right: a single character
repeats with period 1 vacuously.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - a period does not have to divide the length of the prefix - a period is not an occurrence, so overlap does not arise, and `n` periods are wanted
Input
A single line containing the string s, of lowercase English letters.
Output
Print n integers on one line separated by single spaces. The k-th of them, counting from 1, is the smallest period of the first k characters of s.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.