Python-сообщество

Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт

Вам даны две строки s и t, которые состоят из букв ’a’ и ’b’. В строке s нет соседних одина- ковых букв. Вы хотите выбрать наибольшее количество непересекающихся подпоследователь- ностей t, которые равны s. Подпоследовательность — это такая последовательность строки, которая может быть получена удалением нескольких (возможно ноль) элементов из этой строки. Найдите максимальное количество подпоследовательностей, которое вы сможете выбрать.

Формат входных данных


| |
Первая строка входных данных содержит одну строку s (1 ≤ s ≤ 4). Гарантируется, что в строке s нет соседних одинаковых букв.

Вторая строка входных данных содержит одну строку t (1 ≤ |t| ≤ 10^5).



Формат выходных данных
Выведите одно целое число — максимальное количество подпоследовательностей, которое вы сможете выбрать.



Система оценки
Данная задача содержит 7 подзадач, в которых выполняются следующие ограничения:



Тесты из условия. Оценивается в 0 баллов.

|s| = 1. Оценивается в 11 баллов.

|s| = 2. Оценивается в 14 баллов.

|s| = 3. Оценивается в 20 баллов.

|s| = 4, |t| ≤ 50. Оценивается в 18 баллов.

|s| = 4, |t| ≤ 300. Оценивается в 12 баллов.

|s| = 4, |t| ≤ 10^5. Оценивается в 25 баллов.

Примеры


стандартный ввод

стандартный вывод

ab
abbaba


2

aba
ababaa


2

Замечание

Во втором примере можно выбрать две непересекающихся последовательности c индексами 1, 2, 5 и 3, 4, 6.

Отредактировано Danial10 (Ноя. 30, 2022 09:13:38)

Прикреплённый файлы:
EC7FF188-826C-48B2-A94C-AE943499C800.png (37,0 KБ)