102995: [Atcoder]ABC299 F - Square Subsequence
Description
Score : $500$ points
Problem Statement
You are given a string $S$ consisting of lowercase English letters. Print the number of non-empty strings $T$ that satisfy the following condition, modulo $998244353$.
The concatenation $TT$ of two copies of $T$ is a subsequence of $S$ (not necessarily contiguous).
Constraints
- $S$ is a string consisting of lowercase English letters whose length is between $1$ and $100$, inclusive.
Input
The input is given from Standard Input in the following format:
$S$
Output
Print the answer.
Sample Input 1
ababbaba
Sample Output 1
8
The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.
Sample Input 2
zzz
Sample Output 2
1
The only string satisfying the condition is z.
Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from $S = S_1S_2S_3 = $ zzz: $S_1S_2 = $ zz, $S_1S_3 = $ zz, and $S_2S_3 = $ zz.
Sample Input 3
ppppqqppqqqpqpqppqpqqqqpppqppq
Sample Output 3
580
Input
题意翻译
给定一个由小写英文字母组成的字符串 $S$。计算满足以下条件的非空字符串 $T$ 的数量，答案对 $998244353$ 取模。 > 将 $T$ 复制一倍形成 $TT$，则 $TT$ 是 $S$ 的子序列（不一定连续）。Output
分数：500分
问题描述
给你一个由小写英文字母组成的字符串$S$。打印满足以下条件的不同非空字符串$T$的数量（模998244353）。
两个$T$的复制$TT$是$S$的子序列（不一定连续）。
限制条件
- $S$是一个长度在1到100之间的由小写英文字母组成的字符串。
输入
输入数据通过标准输入给出如下格式：
$S$
输出
打印答案。
样例输入1
ababbaba
样例输出1
8
满足条件的8个字符串是 a, aa, ab, aba, b, ba, bab, 和 bb。
样例输入2
zzz
样例输出2
1
满足条件的唯一字符串是z。注意，虽然有三种方法从$S = S_1S_2S_3 = $ zzz中提取子序列zz：$S_1S_2 = $ zz, $S_1S_3 = $ zz, 和 $S_2S_3 = $ zz，但这字符串只贡献一次答案。
样例输入3
ppppqqppqqqpqpqppqpqqqqpppqppq
样例输出3
580