Editing 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
<br>
== Exemplu 2 ==
; subsecventin.txt
: 4
: abba
: abab
: baaa
: aaa
; subsecventout.txt
: 4
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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

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

# 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:
<br>
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.