Editing 0713 - SecvPal1

== Enunt ==
Pentru un şir de caractere S, vom nota cu lmax[S] lungimea maximă a unei secvenţe palindromice conţinută în şirul S. Astfel, pentru şirul S=”abAabaabC”, lmax[S]=4, iar pentru şirul S=”a”, lmax[S]=1.

Prin secvenţa palindromică a unui şir S înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom.
== Cerința ==
Date fiind N şiruri de caractere S[1], S[2],…, S[n] şi o valoare naturală L, se cere să se determine numărul de secvenţe de şiruri de caractere de forma: S[i], S[i+1], … , S[j], cu i<=j, pentru care lmax[S[i]]+lmax[S[i+1]]+... +lmax[S[j]]=L.
== Date de intrare ==
Fișierul de intrare secvpal1in.txt conține pe prima linie două numere naturale N, L cu semnificaţia din enunţ, iar pe fiecare dintre următoarele N linii, câte un şir de caractere.
== Date de ieșire ==
Fișierul de ieșire secvpal1out.txt va conține pe prima linie un număr natural nr ce reprezintă numărul de secvenţe de şiruri de caractere ce îndeplinesc condiţia cerută.
== Restricții și precizări ==
*2 &les; N &les; 50 000;
*0 &les; nr &les; 10 000;
*1 &les; lungimea maximă a oricărui şir S[i] &les; 10 000, 1&les;i&les;N;
*1 &les; lungimea maximă a unei secvenţe palindromice lmax[S[i]] &les; 1 000;
*1 &les; (lungimea maximă şir S[i]) × N &les; 1 000 000;
*Cele N şiruri de caractere conţin doar caracterele ‘A’..’Z’, ’a’..’z’;
*Un palindrom este un şir de caractere care citit de la stânga la dreapta sau de la dreapta la stânga este acelaşi.
== Exemplu 1 ==
;secvpal1in.txt
:5 11
:aCCACCACaBa
:AAPAPAACCAA
:acaacc
:capac
:CACAACAACACCAACP
;secvpal1out.txt
:2
<br>
== Explicație ==
:1. lmax(”aCCACCACaBa”)=6
:2. lmax(”AAPAPAACCAA”)=7
:3. lmax(”acaacc”)=4
:4. lmax(”capac”)=5
:5. lmax(”CACAACAACACCAACP”)=11

Cele două secvenţe de lungime 11 sunt: (2,3) şi (5)
== Exemplu 2 ==
;secvpal1in.txt
: 0
;secvpal1out.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0713 - SecvPal1
def is_palindrome(s):
    return s == s[::-1]

def calculate_lmax(s):
    lmax = 0
    current_length = 0

    for i in range(len(s)):
        current_length = 0
        while i - current_length >= 0 and i + current_length < len(s) and s[i - current_length] == s[i + current_length]:
            current_length += 1

        lmax = max(lmax, current_length * 2 - 1)

    return lmax

def read_input(file_name):
    try:
        with open(file_name, 'r') as file:
            N, L = map(int, file.readline().split())
            strings = [file.readline().strip() for _ in range(N)]

            return N, L, strings
    except Exception as e:
        print(f"Nu au fost respectate cerintele impuse: {str(e)}")
        return None

def write_output(file_name, result):
    with open(file_name, 'w') as file:
        if result is not None:
            file.write(f"{result}\n")

def count_sequences(N, L, strings):
    count = 0

    for i in range(N):
        for j in range(i, N):
            lmax_sum = sum(calculate_lmax(s) for s in strings[i:j+1])
            if lmax_sum == L:
                count += 2

    return count

def main(input_file, output_file):
    result = read_input(input_file)
    if result is not None:
        N, L, strings = result
        result = count_sequences(N, L, strings)
        write_output(output_file, result)

if __name__ == "__main__":
    main("secvpal1in.txt", "secvpal1out.txt")

</syntaxhighlight>