Фабрика палиндромов
Рассмотрим произвольную строку 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).