НачалоПодразделы
Другие разделы
| 1403. Anamorphic |
| 1404. Association |
| 1405. Crap Streak |
| 1406. Disorder |
| 1407. deMorse |
| 1408. Flush |
| 1409. Links |
Дата и время
20/12/2024 16:50:15
1410. String Picker
String Picker
Сложение и вычитание длинных целых, умножение и деление на короткоеДинамическое программирование и запоминающие функции
Олимпиадные задачи на английском языке
| 24/06/2010 | Лето 2010 дорешивание ( 3H) |
| 28/06/2010 | Лето 2010 - 3 (H) |
| 09/01/2017 | Марафон 1 (командный) "Hatter's riddles" (B) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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"
