printРабочее место участника

printЗадачи

1410. String Picker

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

A sequence `x_1\ x_2\ …\ x_m` is a subsequence of `y_1\ y_2\ …\ y_n` if `m\ ≤\ n` and
`x_1\ =\ y_{k_1},\ x_2\ =\ y_{k_2},\ …,\ x_m\ =\ y_{k_m}`, where `1\ ≤\ k_1\ <\ k_2\ <\ …\ <\ k_m\ ≤\ n`.
In this problem, you are given two strings `x\ =\ x_1\ x_2\ …\ x_m` and `y\ =\ y_1\ y_2\ …\ y_n`, and must count the number of ways in which `x` appears as a subsequence of `y`, i.e. the number of distinct index sequences `k_1,\ k_2,\ …,\ k_m` that satisfy the definition of subsequence above. For example, "cat" appears as a subsequence of "chant" in exactly one way, and "ram" appears as a subsequence of "programming" in four ways.
Input Format
Each line of input contains two nonempty strings of lowercase letters `x` and `y`, separated by one or more blanks. A length of any string isn't more 200.
Output Format
For each line of input, report the number of ways in which `x` appears as a subsequence of `y`, as shown in the output sample below.

Sample Input

cat chant
ram programming
cob cocbcob
jog mygojobe
contest contest
fragtastic frag
aa aaaa
aaaa aaaaaaaa
aaaaaa aaaaaaaaaaaa

Sample Output

1 "cat" in "chant"
4 "ram" in "programming"
5 "cob" in "cocbcob"
0 "jog" in "mygojobe"
1 "contest" in "contest"
0 "fragtastic" in "frag"
6 "aa" in "aaaa"
70 "aaaa" in "aaaaaaaa"
924 "aaaaaa" in "aaaaaaaaaaaa"
Source: California State Polytechnic University Programming Contest, Fall 2009
loading