P17451 文回文 / Emordnilap

给定长度为 $n$ 的字符串 $s$，下标从 $1$ 开始。对于每个 $1\le i\le n$，如果以 $i$ 为中心，长度为 $2r+1$ 的子串是回文的，则称非负整数 $r$ 是中心 $i$ 的一个回文半径。 对每个中心 $i$，找到使对应回文子串的字典序最小的回文半径。

**本题有多组测试数据。** 第一行包含一个整数 $T$ ($1\le T\le 10^6$)，表示测试数据组数。 每组数据一行，包含一个非空字符串 $s$。保证 $s$ 仅由小写英文字母构成。 保证 $\sum\lvert s\rvert\le 10^6$。

输出 $T$ 行，每行输出 $\lvert s\rvert$ 个整数，其中第 $i$ 个整数表示中心 $i$ 的答案。

样例第一组测试中，以 $3$ 为中心的回文子串共有三个，分别是 `b`、`aba`、`cabac`，其中字典序最小者为 `aba`，半径为 $1$。