21/11/2024 20:15:24

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

24/06/2010	Лето 2010 дорешивание ( 3H)
28/06/2010	Лето 2010 - 3 (H)
09/01/2017	Марафон 1 (командный) "Hatter's riddles" (B)