Rezolvare PBinfo #3492

Cerința

Se dă un șir s care conține litere mici ale alfabetului englez, urmat de un număr natural k. Să se afișeze câte subsecvențe ale șirului s de lungime 1, 2, … k sunt palindromuri.

Date de intrare

Fișierul de intrare palpal.in conține pe prima linie un șir s și pe următoarea linie un număr natural k.

Date de ieșire

Fișierul de ieșire palpal.out va conține k linii. Pe linia i (1 ≤ i ≤ k) se va găsi numărul de subsecvențe de i caractere care sunt palindromuri.

Restricții și precizări

• 1 ≤ k ≤ 1000
• șirul s are maxim 20000 de caractere
• Prin subsecvență a unui șir de caractere se înțelege o succesiune de unul sau mai multe caractere din șir aflate pe poziții consecutive.
• Un șir de caractere este palindrom dacă se citește la fel de la stânga la dreapta și de la dreapta la stânga.

Exemplu:

palpal.in

eaaebeadaebcc
5

palpal.out

13
2
2
1
2

Explicație

Subsecvențe palindrom de lungime 1: e, a, a, e, b, e, a, d, a, e, b, c, c.
Subsecvențe palindrom de lungime 2: aa, cc.
Subsecvențe palindrom de lungime 3: ebe, ada.
Subsecvențe palindrom de lungime 4: eaae.
Subsecvențe palindrom de lungime 5: aebea, eadae.