eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Фабрика палиндромов

Фабрика палиндромов

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Рассмотрим произвольную строку g. Будем называть эту строку генератором палиндромов. Множество палиндромов P(g), которые генерируются этой строкой определяется следующим образом.

Пусть длина строки равна n. Для всех i от 1 до n в P(g) включаются строки g[1..i]g[1..i]^r и g[1..i]g[1..i-1]^r, где α^r означает α, записанную в обратном порядке.

Например, если g="olymp", то P(g)={"oo", "o", "ollo", "olo", "olyylo", "olylo", "olymmylo", "olymylo", "olymppmylo", "olympmylo"}.

Для заданного генератора палиндромов g и строки s требуется найти количество вхождений строк из P(g) в s как подстрок. А именно, требуется найти количество таких пар (i, j), что s[i..j] P(g).

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

Первая строка входного файла содержит строку g. Вторая строка входного файла содержит s. Обе строки непусты и имеют длину не больше 100000 символов.

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

Выведите в выходной файл количество таких пар (i, j), что s[i..j] P(g).

Пример

Входные данные #1
olymp
olleolleolympmyolylomylo
Выходные данные #1
7