Counting Subsequences Filename: countseq.java Standard Input, Standard Output The Problem Given a sequence of letters as well as subsequence from the original list, you are to count how many times the particular subsequence occurs. Given a sequence c0, c1, … cn-1 of letters, we define a subsequence index list to be some ordered list of integers a0, a1, … am-1. The corresponding subsequence is the string c[a0]c[a1]…c[am-1]. For example, given the string, s = “engineering”, the subsequence defined by the index list 1, 3, 4 and 6 is “nine”, since s[1] = ‘n’, s[3] = ‘i’, s[4] = ‘n’, and s[6] = ‘e’. The number of times a subsequence occurs in a given sequence is simply the number of unique index lists that generate the given subsequence. For the problem at hand, there are two occurrences of the subsequence “nine”. One is the given one and the other is generated by the index list 1, 3, 4 and 5. The Input The first line of the input will contain a single positive integer, n, representing the number of test cases in the file. The following n lines will contain 1 test case each. Each of these lines will have two non-empty strings of lowercase letters separated by a space. The first of these strings is the given input sequence while the second string will be the subsequence for which to search. It is guaranteed that the length of the first string is 1000 or less and that the length of the subsequence is less than or equal to the length of the given sequence. Furthermore, it’s guaranteed that the subsequence appears at least once in the sequence. The Output For each test case, output a single line with the number of occurrences of the given subsequence. The cases will be such that this value is less than 1018 . Sample Input 2 engineering nine sallysellsseashells sell Sample Output 2 21
