e-olymp
Problems

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

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

Рассмотрим произвольную строку 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] TM_in P(g).

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

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

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

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

Time limit 1 second
Memory limit 64 MiB
Input example
olymp
olleolleolympmyolylomylo
Output example
7