2043 - Subsecventa

Cerința

O echipă de cercetători de la Agenţia Spaţială Europeană au recepţionat un mesaj provenit dintr-o altă galaxie. În urma analizelor complexe efectuate asupra mesajului recepţionat, ei au descoperit că mesajul conţine mai multe subsecvenţe neîntrerupte de caractere care sunt palindroame. Se ştie că o secvenţă de caractere este un palindrom dacă prin citirea ei de la stânga la dreapta şi de la dreapta la stânga se obţin aceleaşi caractere. Mesajul recepţionat este codificat doar cu literele mari A, B, …, Z ale alfabetului englez şi nu conţine alte caractere.

Pentru analiza mesajului recepţionat cercetătorii au nevoie de un program care să determine subsecvenţa palindrom de lungime maximă. În cazul în care există mai multe subsecvenţe care au aceeaşi lungime maximă, se va reţine subsecvenţa care apare prima dată în scrierea mesajului, citit de la stânga spre dreapta.

De exemplu, pentru mesajul “CABABAD”, subsecvenţa palindrom cu lungimea maximă este “ABABA” şi are lungimea 5.

Date de intrare

În fișierul de intrare subsecventain.txt este scris şirul de caractere ale mesajului. Mesajul este format doar din litere mari ale alfabetului englez şi are cel mult 100.000 de caractere.

Date de ieșire

Fișierul de ieșire subsecventaout.txt va conține pe prima linie un număr natural reprezentând lungimea maximă a unei subsecvenţe palindrom, iar pe a doua linie se va scrie subsecvenţa palindrom de lungime maximă care apare prima dată în mesaj.

Restricții și precizări

• Mesajul conţine doar litere mari şi are cel mult 100.000 de caractere.
• Pentru 60% din teste numărul de caractere din fişierul de intrare este cel mult 1.000.

Exemplul 1

subsecventain.txt

CABABAD

subsecventaout.txt

5

ABABA

Exemplul 2

subsecventain.txt

6

PALIND

ROMEER

AZBAAZA

MADAAM

ABABA

CIVIC

subsecventaout.txt

5

AZBAAZA

Rezolvare

<syntaxhighlight lang="python" line>

1. 2043 - Subsecventa
2. Citirea datelor de intrare

with open("subsecventain.txt", "r") as f:

   mesaj = f.readline().strip()

1. Verificarea restricțiilor

if not (1 <= len(mesaj) <= 100000 and all('A' <= ch <= 'Z' for ch in mesaj)):

   with open("subsecventaout.txt", "w") as g:
       g.write("Fals\n")

else:

   # Găsirea subsecvenței palindrom de lungime maximă
   def longest_palindrome(s):
       n = len(s)
       start = 0
       max_len = 1

       # Verificare palindrom pentru o subsecvență de lungime impară
       for i in range(1, n):
           low = i - 1
           high = i + 1
           while low >= 0 and high < n and s[low] == s[high]:
               if high - low + 1 > max_len:
                   start = low
                   max_len = high - low + 1
               low -= 1
               high += 1

       # Verificare palindrom pentru o subsecvență de lungime pară
       for i in range(1, n):
           low = i - 1
           high = i
           while low >= 0 and high < n and s[low] == s[high]:
               if high - low + 1 > max_len:
                   start = low
                   max_len = high - low + 1
               low -= 1
               high += 1

       return max_len, s[start:start + max_len]

   # Determinarea rezultatelor
   lungime_maxima, subsecventa_maxima = longest_palindrome(mesaj)

   # Scrierea rezultatelor în fișierul de ieșire
   with open("subsecventaout.txt", "w") as g:
       g.write(str(lungime_maxima) + "\n")
       g.write(subsecventa_maxima + "\n")

</syntaxhighlight>

Explicatie

Cea mai lungă subsecvenţă palindrom are lungimea 5.
Există o singură subsecvenţă palindrom de lungime 5 în mesaj: ABABA.