Задача E. Стильная гирлянда ≡

Условие

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

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

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

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

k₁₁, k₂₁…k_n1, k₁₂…k_n2, …k_nm. Где k_ij =  = k_i.

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

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

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

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

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

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

Ограничения

0 < length(s) ≤ 10⁷

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

acbacabba
abac

4

abac
acbacabba

0

Разбор

Идея решения:

Во-первых нужно понять, что если уже есть какая-то красивая гирлянда и вы пытаетесь удлинить ее, то всегда нужно брать ближайшую подходящую лампочку.

Брать более далекую лампочку бессмыслено, так как из-за этого мы не получим гирлянду короче, только длиннее или такую же.

А значит можно последовательно пробежаться по исходной гирлянде, если встречается подходящая лампочка, то ее берем, если нет - идем дальше.

В ответ выводим длину строки из полных строк k.

Описание реализации:

Пусть count длина стильной гирлянды, которую мы уже собрали.

Циклом проходимся по строке s, если текущий символ совпадает с текущим символом строки k, то увеличиваем count на 1 и берем следующий символ строки k.

В конце выводим count.