Областная олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Задача B. AB

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

Формат входного файла

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

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

Формат выходного файла

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

Примеры

Входные данные

ab
abbaba

Выходные данные

2