Editing 1042 - Subsecvente


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

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

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

= Date de ieșire =
Fișierul de ieșire <code>subsecventeOUT.txt</code> 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 =

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

= Exemplu 1: =
<code>subsecventeIN.txt</code>
 4
 abbabaaaaabb
 aaaababab
 bbbbaaaab
 aaaaaaabaaab
<code>subsecventeOUT.txt</code>
 5

= Explicație =
Lungimea unei subsecvenţe comune de lungime maximă este <code>5</code>.

În exemplu subsecvența comună de lungime <code>5</code> este <code>aaaab</code>:

<code>abbabaaaaabb</code>, <code>aaaababab</code>, <code>bbbbaaaab</code>, <code>aaaaaaabaaab</code>.
:

== Exemplu 2: ==
<code>subsecventeIN.txt</code>
 7
 abbabaaaaabb
 aaaababab
 bbbbaaaab
 aaaaaaabaaab
<code>subsecventeOUT.txt</code>
 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>