Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
2 つの文字列 S, T が与えられます。 S, T いずれかの部分列となっているような文字列の数を 998244353 で割った余りを求めてください。
ただし、文字列 A が文字列 B の部分列であるとは、A の長さが 1 以上であり、B から 0 個以上の文字を取り除くことで A と一致させられることをさします。例えば 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
の 7 つ、
T= bca
の部分列は b
, c
, a
, bc
, ba
, ca
, bca
の 7 つです。
よって、いずれかの部分列となっている文字列は
a
, b
, c
, ab
, ac
, ba
, bc
, ca
, abc
, bca
の 10 個です。
入力例 2
aa aaaaa
出力例 2
5
条件をみたす文字列は a
, aa
, aaa
, aaaa
, aaaaa
の 5 つです。
入力例 3
xzyyzxxzyy yzxyzyxzyx
出力例 3
758
Score : 6 points
Problem Statement
You are given two strings S and T. Find the number of strings that are subsequences of at least one of S and T, modulo 998244353.
Here, a string A is said to be a subsequence of string B when the length of A is at least 1 and A can result from removing zero or more characters from B. For example, atcoder
and ac
are subsequences of atcoder
, while atcoderr
and ca
are not.
Constraints
- 1 \leq \lvert S\rvert, \lvert T\rvert \leq 1000
- S and T consist of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S T
Output
Print the answer.
Sample Input 1
abc bca
Sample Output 1
10
S= abc
has seven subsequences: a
, b
, c
, ab
, ac
, bc
, abc
, while
T= bca
has seven subsequences: b
, c
, a
, bc
, ba
, ca
, bca
.
Therefore, we have ten strings that are subsequences of at least one of them: a
, b
, c
, ab
, ac
, ba
, bc
, ca
, abc
, bca
.
Sample Input 2
aa aaaaa
Sample Output 2
5
The sought strings are a
, aa
, aaa
, aaaa
, aaaaa
.
Sample Input 3
xzyyzxxzyy yzxyzyxzyx
Sample Output 3
758