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