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

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

题目背景

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

题目描述

给定一个字符串 ss。保证每个字符为小写字母。对于 ss 的每个位置,请求出以该位置结尾的回文子串个数。

这个字符串被进行了加密,除了第一个字符,其他字符都需要通过上一个位置的答案来解密。

具体地,若第 i(i1)i(i\geq 1) 个位置的答案是 kk,第 i+1i+1 个字符读入时的 ASCII\rm ASCII 码为 cc,则第 i+1i+1 个字符实际的 ASCII\rm ASCII 码为 (c97+k)mod26+97(c-97+k)\bmod 26+97。所有字符在加密前后都为小写字母。

输入格式

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

输出格式

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

debber

1 1 1 2 1 1

lwk

1 1 2

lxl
1 1 1

提示

对于 100%100\% 的数据, 1s5×1051\leq |s|\leq 5\times 10^5