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 ⩽ N ⩽ 50 000;
• 0 ⩽ nr ⩽ 10 000;
• 1 ⩽ lungimea maximă a oricărui şir S[i] ⩽ 10 000, 1⩽i⩽N;
• 1 ⩽ lungimea maximă a unei secvenţe palindromice lmax[S[i]] ⩽ 1 000;
• 1 ⩽ (lungimea maximă şir S[i]) × N ⩽ 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

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

Rezolvare

#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")