P5496 【模板】回文树 / 回文自动机（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

输入 #1

debber

输出 #1

1 1 1 2 1 1

输入输出样例 #2

输入 #2

lwkvjfrphhgkfvzzyx

输出 #2

1 1 2 2 3 1 1 1 1 2 3 1 1 1 1 2 3 4

输入输出样例 #3

输入 #3

azzzyyzyyx

输出 #3

1 2 1 2 3 2 2 2 3 3

说明/提示

样例解释

三个样例解码后分别为：

• $\verb!dfccgs!$；
• $\verb!lxlxlisqiiingwaaaa!$；
• $\verb!aabaabbaaa!$。

数据范围及约定

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