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

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()