P17451 Emordnilap / Emordnilap

Given a string $s$ of length $n$, with indices starting from $1$. For each $1 \le i \le n$, if the substring of length $2r+1$ centered at $i$ is a palindrome, then the non-negative integer $r$ is called a palindrome radius of center $i$. For each center $i$, find the palindrome radius such that the corresponding palindromic substring is lexicographically smallest.

**This problem has multiple test cases.** The first line contains an integer $T$ ($1 \le T \le 10^6$), which is the number of test cases. Each test case consists of one line containing a non-empty string $s$. It is guaranteed that $s$ contains only lowercase English letters. It is guaranteed that $\sum \lvert s \rvert \le 10^6$.

Output $T$ lines. For each line, output $\lvert s \rvert$ integers, where the $i$-th integer is the answer for center $i$.

In the first test case of the sample, there are three palindromic substrings centered at $3$: `b`, `aba`, and `cabac`. The lexicographically smallest one is `aba`, with radius $1$. Translated by ChatGPT 5