gbvf1

06.10.2022 11:11

Алгебра

Есть ответ 👍

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

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

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

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

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

Тесты из условия. Оценивается в
|s|=1. Оценивается в
|s|=2. Оценивается в
|s|=3. Оценивается в
|s|=4, |t|≤50. Оценивается в
|s|=4, |t|≤300. Оценивается в
|s|=4, |t|≤105. Оценивается в
Примеры
входные данные
ab
abbaba
выходные данные
2
входные данные
aba
ababaa
выходные данные
2