Fişierul intrare/ieşire:revsecv.in, revsecv.outSursăAlgoritmiada 2016 - Runda 2, Seniori
AutorAndrei PopaAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test1.5 secLimită de memorie132768 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Revsecv

Fie un şir de caractere A de forma a0a1a2...an-1 Se defineste inversul şirului A ca fiind Inv(A) = an-1an-2...a1a0, 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 aiai+1ai+2...ai+k-1 = Inv(ajaj+1aj+2...aj+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

revsecv.inrevsecv.out
rabaczeabaca
16
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?