Se numeşte palindrom un cuvânt care citit de la stânga la dreapta sau de la dreapta la stânga este acelaşi. De exemplu, cuvântul cojoc este un palindrom.
Dat fiind un număr natural k, vom numi k-palindrom un cuvânt care se poate transforma într-un palindrom prin înlocuirea a cel mult k litere. De exemplu, pentru k=2, cuvintele cojoc, poloboc, palat sunt 2-palindromuri (am subliniat literele care trebuie să fie înlocuite).
Să considerăm un şir format din litere mici ale alfabetului englez. Un fragment al şirului se obţine prin eliminarea unor litere (0, 1, 2 sau mai multe) de la începutul şi/sau sfârşitul şirului. De exemplu, fragmentele şirului parc sunt p, a, r, c, pa, ar, rc, par, arc, parc.

Cerinţă

Dat fiind un şir de litere mici şi un număr natural k, să se determine câte fragmente din şir sunt k-palindromuri.

Date de intrare

Fişierul de intrare kpal.in conţine pe prima linie numărul natural k. Pe cea de a doua linie se află un şir de litere mici ale alfabetului englez.

Date de ieşire

Fişierul de ieşire kpal.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de fragmente ale şirului dat care sunt k-palindromuri.

Restricţii

• 0 < Lungimea şirului ≤ 5000
• 0 ≤ k ≤ Lungimea şirului

Exemplu

kpal.in	kpal.out	Explicatie
1 abcba	13	Fragmentele care sunt 1-palindrom sunt: a, b, c, b, a ab, bc, cb, ba abc, bcb, cba, abcba

prof. Marinel Serban

Liceul de Informatica "Grigore Moisil" Iasi