07/04/2025 02:47:29

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

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

Задачи

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

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

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

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

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

Задачи

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)