Square Subsequence

题目描述

给你一个仅由小写英文字母组成的字符串 $S$。 输出满足下述条件的非空字符串 $T$ 的数量，对 $998244353$ 取模。

两个拷贝的串 $T$ 的拼接 $TT$ 是 $S$ 的一个子序列（不要求连续）。

输入格式

输入由标准输入给出，格式如下： $S$

输出格式

输出答案。

ababbaba

8

zzz

1

ppppqqppqqqpqpqppqpqqqqpppqppq

580

提示

$S$ 是一个仅由小写英文字母组成的字符串，长度在 $1$ 到 $100$ 之间（包括两端）。满足条件的八个字符串是 $a$, $aa$, $ab$, $aba$, $b$, $ba$, $bab$, 和 $bb$.
唯一满足条件的字符串是 $z$。 注意尽管对于 $S = S_1S_2S_3 =$$zzz$ 可以有三种方式提取子序列 $zz$：$S_1S_2 =$$zz$、$S_1S_3 =$$zz$、和 $S_2S_3 =$$zz$，该字符串只对答案贡献一次。

标签: AtCoder|abc299F

来源

AtCoder|abc299F