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

Розглянемо довільний рядок $\text{g}$. Ми будемо називати цей рядок генератором паліндромів. Множина паліндромів $\text{P(g)}$, згенерована цим рядком, визначається наступним чином:

Нехай довжина рядка дорівнює $n$. Для кожного $i$ від $1$ до $n$, рядки g[1..i]g[1..i]^r та g[1..i]g[1..i-1]^r включаються до $\text{P(g)}$, де \alpha^r позначає зворотний рядок до $\alpha$.

Наприклад, якщо g = \text{olymp}, то P(g) = \{\text{oo}, \text{o}, \text{ollo}, \text{olo}, \text{olyylo}, \text{olylo}, \text{olymmylo}, \text{olymylo}, \text{olymppmylo}, \text{olympmylo}\}.

Дано генератор паліндромів $g$ і рядок $s$. Визначте, скільки разів рядки з $P(g)$ зустрічаються як підрядки в $s$. А саме, знайдіть кількість пар $(i,j)$ таких, що s[i..j] \in P(g).