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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
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:
subsecventeIN.txt
4 abbabaaaaabb aaaababab bbbbaaaab aaaaaaabaaab
subsecventeOUT.txt
5
Explicație
Lungimea unei subsecvenţe comune de lungime maximă este 5
.
În exemplu subsecvența comună de lungime 5
este aaaab
:
abbabaaaaabb
, aaaababab
, bbbbaaaab
, aaaaaaabaaab
.
Exemplu 2:
subsecventeIN.txt
7 abbabaaaaabb aaaababab bbbbaaaab aaaaaaabaaab
subsecventeOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
<syntaxhighlight lang="python" line="1"> import sys
- Definim constantele
NODES = 2600100
- Inițializăm variabilele
p2, lg, mask, i, j, k, p, q, n = 0, 0, 0, 0, 0, 0, 0, 0, 0 s = [[0] * NODES for _ in range(2)] cod = [0] * NODES a = [""] * 50010
def sol(nod):
if not nod or cod[nod] != mask: return 0 sa = sol(s[0][nod]) sb = sol(s[1][nod]) return max(sa, sb) + 1
def main():
global p2, lg, mask, i, j, k, p, q, n # Citim datele de intrare with open("subsecventeIN.txt", "r") as infile: data = infile.read().strip().split()
n = int(data[0]) sequences = data[1:]
# Verificăm restricțiile if not (1 < n < 5) or sum(len(seq) for seq in sequences) >= 50001: with open("subsecventeOUT.txt", "w") as outfile: outfile.write("Datele nu corespund restrictiilor impuse\n") return
p2 = 1 n = 1 mask = 0 for sequence in sequences: lg = len(sequence) mask |= p2 for i in range(1, lg + 1): j = min(i + 59, lg) p = 1 for k in range(i, j + 1): q = ord(sequence[k-1]) - ord('a') if not s[q][p]: s[q][p] = n + 1 n += 1 p = s[q][p] cod[p] |= p2 p2 <<= 1
cod[1] = mask result = sol(1) - 1 with open("subsecventeOUT.txt", "w") as outfile: outfile.write(f"{result}\n")
if __name__ == "__main__":
main()
</syntaxhighlight>