-
Notifications
You must be signed in to change notification settings - Fork 9
/
10069-Distinct Subsequences.java
32 lines (31 loc) · 1.07 KB
/
10069-Distinct Subsequences.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.math.BigDecimal;
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tc;
tc = sc.nextInt();
for(int t=0;t<tc;t++){
String str, sub;
str = sc.next();
sub = sc.next();
BigDecimal[] dp = new BigDecimal[str.length()+1];
Arrays.fill(dp, BigDecimal.valueOf(1));
for(int i=0;i<sub.length();i++){
char c1=sub.charAt(i);
BigDecimal[] dpNext = new BigDecimal[str.length()+1];
dpNext[0] = BigDecimal.valueOf(0);
for(int j=0;j<str.length();j++){
char c2=str.charAt(j);
dpNext[j+1] = BigDecimal.valueOf(0);
if(c1 == c2) {
dpNext[j+1] = dpNext[j+1].add(dp[j]);
}
dpNext[j+1] = dpNext[j+1].add(dpNext[j]);
}
dp = dpNext;
}
System.out.println(dp[str.length()]);
}
}
}