#P5496. 【模板】回文自动机(PAM)
【模板】回文自动机(PAM)
题目背景
模板题,无背景(其实是我想不出背景)。
题目描述
给定一个字符串 。保证每个字符为小写字母。对于 的每个位置,请求出以该位置结尾的回文子串个数。
这个字符串被进行了加密,除了第一个字符,其他字符都需要通过上一个位置的答案来解密。
具体地,若第 个位置的答案是 ,第 个字符读入时的 码为 ,则第 个字符实际的 码为 。所有字符在加密前后都为小写字母。
输入格式
一行一个字符串 表示被加密后的串。
输出格式
一行, 个整数。第 个整数表示原串以第 个字符结尾的回文子串个数。
debber
1 1 1 2 1 1
lwk
1 1 2
lxl
1 1 1
提示
对于 的数据, 。