Editing 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 &les; k &les; 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
<br>
== Exemplu 2 ==
; palpalin.txt'
 eaaebeadaebcc
 -5
; palpalout.txt
 Datele de intrare nu corespund restrictiilor impuse
<br>
== 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>