/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 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