3492 - PalPal

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 palpalin.txt 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 palpalout.txt 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 1

palpalin.txt'

eaaebeadaebcc
5

palpalout.txt

Datele de intrare corespund restrictiilor impuse
13
2
2
1
2

Exemplu 2

palpalin.txt'

eaaebeadaebcc
-5

palpalout.txt

Datele de intrare nu corespund restrictiilor impuse

Explicatie

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.

Rezolvare

<syntaxhighlight lang="python" line> def is_palindrome(s):

   #Verifică dacă un șir de caractere este palindrom.

   return s == s[::-1]

def count_palindromic_subsequences(s, k):

   #Numără subsecvențele palindromice de lungime 1, 2, ..., k ale unui șir.

   counts = [0] * k
   for length in range(1, k + 1):
       for i in range(len(s) - length + 1):
           if is_palindrome(s[i:i+length]):
               counts[length-1] += 1
   return counts

def main():

   with open('palpalin.txt', 'r') as fin, open('palpalout.txt', 'w') as fout:
       s = fin.readline().strip()
       k = int(fin.readline().strip())

       # Verifică dacă datele de intrare respectă restricțiile
       if len(s) > 20000 or k < 1 or k > 1000:
           fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
           return

       fout.write("Datele de intrare corespund restrictiilor impuse\n")

       # Numără subsecvențele palindromice și scrie rezultatele în fișierul de ieșire
       counts = count_palindromic_subsequences(s, k)
       for count in counts:
           fout.write(str(count) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>