Fişierul intrare/ieşire:	revsecv.in, revsecv.out	Sursă	Algoritmiada 2016 - Runda 2, Seniori
Autor	Andrei Popa	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.75 sec	Limită de memorie	132768 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Revsecv

Fie un şir de caractere A de forma a₀a₁a₂...a_n-1 Se defineste inversul şirului A ca fiind Inv(A) = a_n-1a_n-2...a₁a₀, adica şirul de caractere care se obtine scriind caracterele lui A în ordine inversa.

Câte triplete i j k cu 0 ≤ i ≤ i + k - 1 ≤ n - 1, i + k ≤ j ≤ j + k - 1 ≤ n - 1 există astfel încât a_ia_i+1a_i+2...a_i+k-1 = Inv(a_ja_j+1a_j+2...a_j+k-1). Cu alte cuvinte, câte perechi de subsecvenţe de lungime egală disjuncte ale lui A au proprietatea că cea de a doua dintre ele este inversa celei dintâi?

Date de intrare

Fişierul de intrare revsecv.in va conţine pe unica sa linie şirul A.

Date de ieşire

În fişierul de ieşire revsecv.out se va afla un singur număr natural, răspunsul la întrebarea din enunţ.

Restricţii

• 1 ≤ |A| ≤ 100.000
• Pentru teste in valoare de 20 de puncte |A| ≤ 200
• Pentru teste in valoare de 40 de puncte |A| ≤ 5.000
• Caracterele lui A sunt litere mici ale alfabetului englez.

Exemplu

Cum se trimit solutii?