[SNCPC2024] 双子序列
题目描述
小 L 看到不喜欢的字符串就很难受!看到它作为子序列出现也是!
给定一个长字符串 $S$ 表示小 L 要阅读的文本,以及恰好两个短字符串 $s_1$,$s_2$ 表示小 L 不想看到的字符串,三个字符串均由小写字母组成。
小 L 很反感这两个字符串作为子序列在文本内同时出现,他认为,一个字符串 $T$ 的反感度为:$s_1$ 作为 $T$ 的子序列的出现次数,和 $s_2$ 作为 $T$ 的子序列的出现次数之积。
由于他要读 $S$ 的每个子串,所以现在需要你求出 $S$ 的所有子串的反感度值之和。由于答案可能过大,你只需要输出对 $998244353$ 取模的结果。
定义一个字符串 $H$ 是 $T$ 的子串,当且仅当 $H$ 由 $T$ 删除最前面的若干字符和最后面的若干字符获得(前缀后缀可以一个字符都不删除,也可以把整个串全删除得到空串)。
定义一个字符串 $H$ 是 $T$ 的子序列,当且仅当 $H$ 由 $T$ 删除若干字符后获得(可以一个字符都不删除,也可以全删除后得到空子序列)。
输入输出格式
输入格式
输入包括三行,每行一个仅由小写字母组成的字符串。
第一行的字符串代表 $S$,第二行代表 $s_1$,第三行代表 $s_2$。其中 $1\le |S|\le 1\times 10^5$,$1\le |s_1|,|s_2|\le 20$。
输出格式
输出一个整数代表求得的答案。
输入输出样例
输入样例 #1
iccpcicpc
icpc
ccpc
输出样例 #1
133
说明
| 子串起始位置 | 子串终止位置 | icpc 次数 | ccpc 次数 |
| :----------: | :----------: | :----------: | :----------: |
| 1 | 5 | 2 | 1 |
| 1 | 6 | 2 | 1 |
| 1 | 7 | 4 | 2 |
| 1 | 8 | 4 | 2 |
| 1 | 9 | 11 | 9 |
| 2 | 5 | 0 | 1 |
| 2 | 6 | 0 | 1 |
| 2 | 7 | 0 | 2 |
| 2 | 8 | 0 | 2 |
| 2 | 9 | 1 | 9 |
| 3 | 9 | 1 | 3 |
| 4 | 9 | 1 | 1 |
| 5 | 9 | 1 | 1 |
| 6 | 9 | 1 | 0 |
在其余的子串内,两个字符串作为子序列的出现次数均为 $0$。
答案为 $(2\times 1) \times 2 + (4\times 2) \times 2 + 11\times 9 + (0\times 1)\times 2 + (0\times 2)\times 2 + 1\times 9 + 1\times 3+ (1\times 1)\times 2 + 1\times 0=133$。