Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1010
A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence X = x1x2 . . . xm, another sequence Z = z1z2 . . . zk is a subsequence of X if there exists a strictly increasing sequence < i1, i2, . . . , ik > of indices of X such that for all j = 1, 2, . . . , k, we have xij = zj . For example, Z = bcdb is a subsequence of X = abcbdab with corresponding index sequence < 2, 3, 5, 7 >. In this problem your job is to write a program that counts the number of occurrences of Z in X as a subsequence such that each has a distinct index sequence. Input The first line of the input contains an integer N indicating the number of test cases to follow. The first line of each test case contains a string X, composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second line contains another string Z having length no greater than 100 and also composed of only lowercase alphabetic characters. Be assured that neither Z nor any prefix or suffix of Z will have more than 10100 distinct occurrences in X as a subsequence. Output For each test case in the input output the number of distinct occurrences of Z in X as a subsequence. Output for each input set must be on a separate line.
Sample Input 2 babgbag bag rabbbit rabbit
Sample Output 5 3
Code Examples
#1 Code Example with C Programming
Code -
C Programming
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 i&It 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 i&It 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 i&It 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()]);
}
}
}Input
babgbag
bag
rabbbit
rabbit
Output
3
Demonstration
UVA Online Judge solution - 10069 - Distinct Subsequences - UVA Online Judge solution in C,C++,Java