Palindrom Sorgusu

Queries for Number of Palindromes

En fazla 5000 uzunluğunda bir stringimiz var. İngiliz alfabesinin küçük harflerinden oluşuyor. Size yapılan sorgularda verilen aralıkta kaç tane palindrom substring(altdizi) olduğuna cevap vermeniz isteniyor. Girdinin ilk satırında string, ikinci satırında sorgu sayısı girilecek. (En fazla 1.000.000 sorgu). Ardından gelen her bir satırda sorgunun aralığını belirten iki sayı bulunacak. Bu sayılar içinde kaç tane palindrom substring geçtiği sorulan aralığın baş ve son indisleridir.

Örnek Girdi

caaaba

5

1 1

1 4

2 3

4 6

4 5

Örnek Çıktı

1

7

3

4

2

_________________________________________________________________________________

LİNKLER:

Soru:  codeforces.com/contest/245/problem/H

Çözüm:  codeforces.com/blog/entry/5921

Örnek Kod:  codeforces.com/contest/245/submission/3289146 (burakbugrul)

_________________________________________________________________________________

Türkçe Çözüm Açıklaması:

Coming Soon.