【模板】回文自动机(PAM)

题目背景

模板题,无背景(其实是我想不出背景)。

题目描述

给定一个字符串 $s$。保证每个字符为小写字母。对于 $s$ 的每个位置,请求出以该位置结尾的回文子串个数。 这个字符串被进行了加密,除了第一个字符,其他字符都需要通过上一个位置的答案来解密。 具体地,若第 $i(i\geq 1)$ 个位置的答案是 $k$,第 $i+1$ 个字符读入时的 $\rm ASCII$ 码为 $c$,则第 $i+1$ 个字符实际的 $\rm ASCII$ 码为 $(c-97+k)\bmod 26+97$。所有字符在加密前后都为小写字母。

输入输出格式

输入格式


一行一个字符串 $s$ 表示被加密后的串。

输出格式


一行, $|s|$ 个整数。第 $i$ 个整数表示原串以第 $i$ 个字符结尾的回文子串个数。

输入输出样例

输入样例 #1

debber

输出样例 #1

1 1 1 2 1 1

输入样例 #2

lwk

输出样例 #2

1 1 2

输入样例 #3

lxl

输出样例 #3

1 1 1

说明

对于 $100\%$ 的数据, $1\leq |s|\leq 5\times 10^5$。