Oros Ioana Diana at 07:20, 18 May 2024

2024-05-18T07:20:48Z

Oros Ioana Diana: Pagină nouă: 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ă: 'abbbaabab...

2024-01-08T23:07:39Z

Pagină nouă: 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ă: 'abbbaabab...

New page

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.

1042 - Subsecvente - Revision history

Oros Ioana Diana at 07:20, 18 May 2024