O35. Стильная гирлянда

Автор:Завгороднев А.А.,Бадерик П.М.  
Входной файл:Стандартный вход  
Выходной файл:Стандартный выход  

В преддверии нового года дед мороз наколдовал гирлянду, которая представляет из себя последовательность разноцветных лампочек.

Однако полученная гирлянда не соответствует стилю 2024 года, из-за чего дед мороз поручил своим эльфам вырвать из гирлянды наименьшее количество лампочек так, чтобы полученная гирлянда соответствовала стилю 2024 года.

Изначальная гирлянда задается строкой s. Гирлянда является стильной, если она состоит из последовательно соединенных строк k.

Более формально если строка k = k1, k2, …, kn, то стильная гирлянда будет представлять из себя последовательность следующего вида:

k11, k21kn1, k12kn2, …knm. Где kij =  = ki.

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

Первая строка входных данных - s.

Вторая строка - k.

Гарантируется, что обе строки состоят только из латинских букв. (строчных и прописных)

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

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

Ограничения

0 < length(s) ≤ 107

Примеры тестов

Стандартный вход Стандартный выход
1
acbacabba
abac
4
2
abac
acbacabba
0

0.069s 0.010s 13