1846. Which Prefixes Are Built From Whole Blocks
For every k from 1 to n, decide whether the prefix s[0..k-1] is some STRICTLY
SHORTER block written out a whole number of times. Print a line of n
characters: 1 where it is and 0 where it is not.
aabaabaab -> 010001001
aaaa -> 0111
abcdef -> 000000
ababa -> 00010
aab -> 010
Read aabaabaab. The prefix aa is a twice, so position 2 is 1. The prefix
aabaab is aab twice, and aabaabaab is aab three times. Nothing else
qualifies.
Read ababa. Every prefix from the second onwards has period 2, yet only the
prefix of length 4 is a whole repetition, because 2 has to DIVIDE the length.
Answering by period alone prints 00111, which was confirmed by running it.
Problem 1807 asks this for the whole string and prints the block length; here every prefix gets a yes or no.
## What most people try first
For each k, try every divisor of k and rebuild the candidate. Rebuilding
costs k characters, and summing over all k and all divisors is well past
10^9 at n = 200000. The method below is O(n), about 4 * 10^5.
## One prefix function, then a remainder
p = k - pi[k-1] the smallest period, from problem 1845
print 1 if p < k and k mod p == 0, else 0
## Why both conditions are needed and why they are enough
p < k is the word STRICTLY: a block as long as the prefix is not shorter than
it, so a single character never qualifies.
k mod p == 0 is what turns a period into a repetition. A period only says the
characters agree p apart; the prefix is a whole number of copies of its first
p characters exactly when p divides k.
That the SMALLEST period is the only one worth testing is the argument from
problem 1807: if the prefix is any block repeated, its smallest period divides
its length, so checking p alone is complete.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - the block must be strictly shorter than the prefix, so the first character is always `0` - the copies inside a prefix sit end to end and never overlap, and a yes or no is wanted per prefix rather than a count
Input
A single line containing the string s, of lowercase English letters.
Output
Print one line of exactly n characters. The k-th of them, counting from 1, is 1 if the first k characters of s are a strictly shorter block repeated a whole number of times, and 0 otherwise.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.