← 返回题目列表

AtCoder · past202206_k

K. 子序列

中文机器翻译题面 查看原题

分数: 6 点

问题陈述

给你两个字符串 S 和 T。 查找至少属于以下之一的子序列的字符串数量 S 和 T,模数 998244353.

这里是一个字符串 A 据说是字符串的子序列 B 当长度 A 至少 1 和 A 可能是由于从其中删除零个或多个字符而导致的 B。例如, atcoder 和 ac 是子序列 atcoder,同时 atcoderr 和 ca 不是。

约束

  • 1 \leq \lvert S\rvert, \lvert T\rvert \leq 1000
  • S 和 T 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

S
T

输出

打印答案。


示例输入 1

abc
bca

示例输出 1

10

S= abc 有七个子序列: a, b, c, ab, ac, bc, abc,同时 T= bca 有七个子序列: b, c, a, bc, ba, ca, bca。 因此,我们有十个字符串,它们至少是其中之一的子序列: a, b, c, ab, ac, ba, bc, ca, abc, bca.


示例输入 2

aa
aaaaa

示例输出 2

5

寻找的字符串是 a, aa, aaa, aaaa, aaaaa.


示例输入 3

xzyyzxxzyy
yzxyzyxzyx

示例输出 3

758