A subsequence of a given sequence \(S\) consists of \(S\) with zero or more elements deleted. Formally, a sequence \(Z = z_1, z_2, \ldots, z_k\) is a subsequence of \(X = x_1, x_2, \ldots, x_m\) if there exists a strictly increasing sequence \(< i_1, i_2, \ldots, i_k >\) of indices of \(X\) such that for all \(j = 1, 2, \ldots, k\) we have \(x_{i_j} = z_j\). For example, \(Z = bcdb\) is a subsequence of \(X = abcbdab\) with corresponding index sequence \(< 2, 3, 5, 7 >\).
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.
The input consists of a number of lines, each specifying a test case. Each line consists of two strings separated by a space character. The first is string \(X\), composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second is 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 \(10^{100}\) distinct occurrences in \(X\) as a subsequence.
An empty line terminates the input.
For each test case, output the number of distinct occurrences of \(Z\) in \(X\) as a subsequence, each on a separate line.
babgbag bag
rabbbit rabbit
5
3
This is challenge 10131 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.
Please log in to submit your solution.
Difficulty 

Average test runtime  0.27 
Points (changes over time)  10 
Tried by  4 users 
Solved by  3 users 
#  Name  Runtime  Points worth 

1  贝尔恩德  0.15  16 
2  Mac  0.33  7 
3  Dark  0.34  7 