1835. How Many Palindromes Start Here
For every position i of s, print how many palindromic pieces of s BEGIN at
i.
aaa -> 3 2 1
abc -> 1 1 1
abba -> 2 2 1 1
racecar -> 2 2 2 1 1 1 1
aabaabaab -> 4 3 3 3 2 2 2 1 1
Every position starts at least one palindrome, the single character there, so no value is ever 0. The values sum to the total from problem 1832, which asks for that sum alone.
Read abba. Position 0 starts a and abba, so 2. Position 1 starts b and
bb, so 2. Positions 2 and 3 start one each.
## What most people try first
For each start, test every end. That is O(n^2) pieces and O(n) to test each,
so O(n^3); even with a quadratic table it is O(n^2), which is 4 * 10^10 at
n = 200000. The method below is about 6 * 10^5.
## Each centre contributes to a contiguous run of starts
Build d1 and d2 with Manacher. An odd centre c with d1[c] palindromes
gives one palindrome starting at each of c, c-1, ..., c - d1[c] + 1: that
is a contiguous RANGE of starting positions, one palindrome each.
An even centre whose right half starts at c, with d2[c] palindromes, gives
one starting at each of c-1, c-2, ..., c - d2[c], again contiguous.
So the answer is a sum of range additions, which a difference array turns into one pass:
for each c:
if d1[c] > 0: diff[c - d1[c] + 1] += 1; diff[c + 1] -= 1
if d2[c] > 0: diff[c - d2[c]] += 1; diff[c] -= 1
answer[i] = running total of diff up to i
## Why the ranges are contiguous
Shrinking a palindrome by one character at each end leaves a palindrome with the same centre whose start has moved one step to the RIGHT. Doing that repeatedly walks the start from the outermost position inwards, one position at a time, with no gaps. That is what makes a range addition the right tool rather than a list of individual positions.
## The parity that is easy to get backwards
The odd range ends at c itself, because the smallest odd palindrome centred at
c is the single character starting at c. The even range ends at c - 1,
because the smallest even palindrome with right half starting at c is two
characters starting at c - 1. Using c for both double counts the single
characters and answers 3 3 2 2 on abba.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - every position starts at least one palindrome, the single character there - palindromic pieces starting at one position may overlap each other, and one count per position 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 how many palindromic pieces of s begin at position i.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.