1042 - Subsecvente

Fie n un număr natural și M={S1,S2,…,Sn} o mulțime de șiruri de caractere nevide. Fie Sk un șir de caractere din M. Atunci, orice caracter al lui Sk aparține mulțimii {'a','b'}. Notăm prin |Sk| numărul caracterelor șirului Sk sau, echivalent, lungimea sa. O subsecvență Sk[i:j] a lui Sk este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j. Astfel, dacă Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecvența evidențiată: 'abbbaababa'.

Cerința

Fiind dată o mulțime M, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din M.

Date de intrare

Fișierul de intrare subsecventein.txt conține pe prima linie un număr natural n egal cu cardinalul mulțimii M. Pe fiecare din următoarele n linii se găsește câte un șir din mulțimea M.

Date de ieșire

Fișierul de ieșire subsecventeout.txt va conține pe prima linie un singur număr natural egal cu lungimea subsecvenței găsite.

Restricții și precizări

• 1 < n < 5
• Dacă |S| = |S1| + |S2| + … + |Sn|, atunci |S| < 50 001
• Se garantează că va exista întotdeauna soluție
• Se garantează că rezultatul nu va depăși 60
• Pentru 30% din teste: |S| < 101
• Pentru 55% din teste: |S| < 3 501
• Pentru 80% din teste: |S| < 10 001

Exemplu 1

subsecventin.txt

4

abbabaaaaabb

aaaababab

bbbbaaaab

aaaaaaabaaab

subsecventeout.txt

5

Exemplu 2

subsecventin.txt

4

abba

abab

baaa

aaa

subsecventout.txt

4

Rezolvare

<syntaxhighlight lang="python" line>

1. 1042 - Sudef lungime_subsecventa_maxima(M):

   # Verificare restricții
   if not (1 < len(M) < 5):
       return "Fals"

   total_length = sum(len(s) for s in M)

   if not (total_length < 50001 and total_length > 0):
       return "Fals"

   chars_set = set(M[0])

   for char in chars_set:
       count = min(s.count(char) for s in M)
       if count < 1:
           return "Fals"

   result = sum(min(s.count(char) for s in M) for char in chars_set)
   return result

1. Citirea datelor de intrare din fișierul "subsecventein.txt"

try:

   with open("subsecventein.txt", "r") as file:
       n = int(file.readline())
       M = [file.readline().strip() for _ in range(n)]

except Exception as e:

   print("Fals")
   exit()

1. Calcularea și afișarea rezultatului în fișierul "subsecventeout.txt"

result = lungime_subsecventa_maxima(M)

if result == "Fals":

   print(result)

else:

   with open("subsecventeout.txt", "w") as file:
       file.write(str(result) + "\n")

bsecvente

</syntaxhighlight>

Explicatie

Lungimea unei subsecvenţe comune de lungime maximă este 5.

În exemplu subsecvența comună de lungime 5 este aaaab:
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.