eolymp
bolt
Try our new interface for solving problems
Məsələlər

Polindromlar 2

Polindromlar 2

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Sətir soldan sağa və sağdan sola eyni cür oxunarsa, polindrom adlanır. Məsələn, "abba" – polindrom, "omax" isə polindrom deyil. α sətri üçün α[i..j]-ni uzunluğu j - i + 1 (i-dən j-yə qədər mövqe) olaraq təyin edəcəyik (mövqe 1-dən başlayır).

Uzunluğu n (1n5000000) olan α sətri üçün α[i..j] polindrom olan q cütlüklərinin sayını (i, j), 1i < jn təyin etmək tələb olunur.

Giirş verilənləri

Uzunluğu n olan kiçik latın hərflərini ehtiva edən α sətri.

Çıxış verilənləri

Cari q cütlüklərinin sayı.

Nümunə

Giriş verilənləri #0
ab

Çıxış verilənləri #0
2

Giriş verilənləri #1
abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba
Çıxış verilənləri #1
769