AT_abc299_f [ABC299F] Square Subsequence

题目描述

给定一个只包含小写英文字母的字符串 $S$。请输出满足以下条件的非空字符串 $T$ 的个数，对 $998244353$ 取模。

将 $T$ 连续连接两次得到的字符串 $TT$，可以作为 $S$ 的（不一定连续的）子序列出现。

输入格式

输入以以下格式从标准输入给出。

$S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

ababbaba

输出 #1

8

输入输出样例 #2

输入 #2

zzz

输出 #2

1

输入输出样例 #3

输入 #3

ppppqqppqqqpqpqppqpqqqqpppqppq

输出 #3

580

说明/提示

限制条件

• $S$ 是一个只包含小写英文字母的字符串，长度满足 $1 \leq |S| \leq 100$。

样例解释 1

满足题目条件的字符串 $T$ 有 $8$ 个，分别是：a、aa、ab、aba、b、ba、bab、bb。

样例解释 2

满足题目条件的字符串 $T$ 只有 z。$S = S_1S_2S_3 = zzz$，可以通过 $S_1S_2 = zz$、$S_1S_3 = zz$、$S_2S_3 = zz$ 这三种方式得到字符串 zz 作为子序列，但字符串 z 只计入答案一次。

由 ChatGPT 4.1 翻译