1836. The Longest Palindrome Inside Each Prefix
For every i from 0 to n-1, print the length of the longest palindromic piece
contained in s[0..i].
abacaba -> 1 1 3 3 3 5 7
aaaa -> 1 2 3 4
abcde -> 1 1 1 1 1
cbbd -> 1 1 2 2
abba -> 1 1 2 4
The answer never decreases, because a palindrome inside a prefix is also inside every longer prefix.
## What most people try first
For each prefix, run the whole longest-palindrome search again. That is n
searches of O(n) each with Manacher, so O(n^2), which is 4 * 10^10 at
n = 200000. Rebuilding is the instinct and it is the expensive part. The
method below is about 8 * 10^5.
## The answer grows by at most two
Let best[i] be the answer for the prefix ending at i. Then
best[i] <= best[i-1] + 2
because if a palindrome of length L ends at i with L > best[i-1] + 2, then
dropping its first and last characters leaves a palindrome of length L - 2
ending at i - 1, and L - 2 > best[i-1] contradicts the definition of
best[i-1].
So at each step only three possibilities need testing, and the first one that works wins:
best[0] = 1
for i in 1 .. n-1:
if the piece of length best[i-1] + 2 ending at i is a palindrome:
best[i] = best[i-1] + 2
else if the piece of length best[i-1] + 1 ending at i is a palindrome:
best[i] = best[i-1] + 1
else:
best[i] = best[i-1]
Each test is one array read, using the constant-time palindrome test built from Manacher in problem 1833.
## Why both the plus two and the plus one are needed
Plus two covers a palindrome that extends the previous best at both ends, which
keeps the parity. Plus one covers a change of parity: on cbbd the best goes
from 1 at position 1 to 2 at position 2, gaining one rather than two, because
bb is even while the previous best c was odd. Testing only plus two answers
1 1 1 1 there.
Nothing smaller than best[i-1] ever needs testing, because best never
decreases.
## The boundary
At i the piece of length L ending there starts at i - L + 1, which must be
at least 0. With L = best[i-1] + 2 that can be negative near the start of the
string, so the index has to be checked before the array is read.
## Cost
O(n) time and O(n) memory: one Manacher and one sweep with at most two
constant-time tests per position.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - the sequence printed never decreases - palindromic pieces may overlap each other freely, and one length per prefix is 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 i-th of them, counting from 0, is the length of the longest palindromic piece contained in the first i + 1 characters of s.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.