2043 - Subsecventa: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == Cerința == O echipă de cercetători de la Agenţia Spaţială Europeană au recepţionat un mesaj provenit dintr-o altă galaxie. În urma analizelor complexe efectuate asupra mesajului recepţionat, ei au descoperit că mesajul conţine mai multe subsecvenţe neîntrerupte de caractere care sunt palindroame. Se ştie că o secvenţă de caractere este un palindrom dacă prin citirea ei de la stânga la dreapta şi de la dreapta la stânga se obţin aceleaşi caractere....
 
No edit summary
 
Line 1: Line 1:
== Cerința ==
= Cerința =
O echipă de cercetători de la Agenţia Spaţială Europeană au recepţionat un mesaj provenit dintr-o
O echipă de cercetători de la Agenţia Spaţială Europeană au recepţionat un mesaj provenit dintr-o
altă galaxie. În urma analizelor complexe efectuate asupra mesajului recepţionat, ei au descoperit că
altă galaxie. În urma analizelor complexe efectuate asupra mesajului recepţionat, ei au descoperit că
mesajul conţine mai multe subsecvenţe neîntrerupte de caractere care sunt palindroame. Se ştie că o
mesajul conţine mai multe subsecvenţe neîntrerupte de caractere care sunt palindroame. Se ştie că o
secvenţă de caractere este un palindrom dacă prin citirea ei de la stânga la dreapta şi de la dreapta la
 
secvenţă de caractere este un ''palindrom'' dacă prin citirea ei de la stânga la dreapta şi de la dreapta la
 
stânga se obţin aceleaşi caractere. Mesajul recepţionat este codificat doar cu literele mari A, B, …, Z
stânga se obţin aceleaşi caractere. Mesajul recepţionat este codificat doar cu literele mari A, B, …, Z
ale alfabetului englez şi nu conţine alte caractere.
ale alfabetului englez şi nu conţine alte caractere.


Pentru analiza mesajului recepţionat cercetătorii au nevoie de un program care să determine subsecvenţa palindrom de lungime maximă. În cazul în care există mai multe subsecvenţe care au aceeaşi lungime maximă, se va reţine subsecvenţa care apare prima dată în scrierea mesajului, citit de la stânga spre dreapta.
Pentru analiza mesajului recepţionat cercetătorii au nevoie de un program care să determine subsecvenţa palindrom de lungime maximă. În cazul în care există mai multe subsecvenţe
 
care au aceeaşi lungime maximă, se va reţine subsecvenţa care apare prima dată
 
în scrierea mesajului, citit de la stânga spre dreapta.


De exemplu, pentru mesajul “CABABAD”, subsecvenţa palindrom cu lungimea maximă este “ABABA” şi are lungimea 5.
De exemplu, pentru mesajul “CABABAD”, subsecvenţa palindrom cu lungimea maximă este “ABABA” şi are lungimea 5.
== Date de intrare ==
 
În fișierul de intrare subsecventain.txt este scris şirul de caractere ale mesajului. Mesajul este format doar din litere mari ale alfabetului englez şi are cel mult 100.000 de caractere.
= Date de intrare =
== Date de ieșire ==  
În fișierul de intrare <code>subsecventaIN.txt</code> este scris şirul de caractere ale mesajului. Mesajul este format
Fișierul de ieșire subsecventaout.txt va conține pe prima linie un număr natural reprezentând lungimea
 
maximă a unei subsecvenţe palindrom, iar pe a doua linie se va scrie subsecvenţa palindrom de lungime maximă care apare prima dată în mesaj.
doar din litere mari ale alfabetului englez şi are cel mult 100.000 de caractere.
== Restricții și precizări ==
 
*Mesajul conţine doar litere mari şi are cel mult 100.000 de caractere.
= Date de ieșire =
*Pentru 60% din teste numărul de caractere din fişierul de intrare este cel mult 1.000.
Fișierul de ieșire <code>subsecventaOUt.txt</code> va conține pe prima linie un număr natural reprezentând lungimea
== Exemplul 1 ==
 
; subsecventain.txt
maximă a unei subsecvenţe palindrom, iar pe a doua linie se va scrie subsecvenţa
: CABABAD
 
; subsecventaout.txt
palindrom de lungime maximă care apare prima dată în mesaj. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
: 5
 
: ABABA
= Restricții și precizări =
<br>
 
== Exemplul 2 ==
* Mesajul conţine doar litere mari şi are cel mult <code>100.000</code> de caractere.
; subsecventain.txt
* Pentru 60% din teste numărul de caractere din fişierul de intrare este cel mult <code>1.000</code>.
: 6
 
: PALIND
= Exemplu 1: =
: ROMEER
<code>subsecventaIN.txt</code>
: AZBAAZA
CABABAD
: MADAAM
<code>subsecventaOUT.txt</code>
: ABABA
5
: CIVIC
ABABA
; subsecventaout.txt
 
: 5
=== Explicație ===
: AZBAAZA
Cea mai lungă subsecvenţă palindrom are lungimea 5.
 
== Exemplu 2: ==
<code>subsecventaIN.txt</code>
CABABADa
<code>subsecventaOUT.txt</code>
Datele nu corespund restrictiilor impuse
<br>
<br>
== Rezolvare ==  
== Rezolvare ==  
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line="1">
#2043 - Subsecventa
def citire(file_in):
# Citirea datelor de intrare
    with open(file_in, 'r') as fin:
with open("subsecventain.txt", "r") as f:
        s = fin.read().strip()
     mesaj = f.readline().strip()
     return s
 
def init(s):
    n = len(s)
    t = ['^']
    for char in s:
        t.append('#')
        t.append(char)
    t.append('#')
    t.append('\0')
    return ''.join(t)
 
def manacher(t):
    n = len(t)
    P = [0] * n
    C = R = 0
    maxpal = 1
 
    for i in range(1, n - 1):
        j = 2 * C - i
        if R > i:
            P[i] = min(R - i, P[j])
 
        while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
            P[i] += 1
 
        if i + P[i] > R:
            C = i
            R = i + P[i]


# Verificarea restricțiilor
        if P[i] > P[maxpal]:
if not (1 <= len(mesaj) <= 100000 and all('A' <= ch <= 'Z' for ch in mesaj)):
            maxpal = i
    with open("subsecventaout.txt", "w") as g:
        g.write("Fals\n")
else:
    # Găsirea subsecvenței palindrom de lungime maximă
    def longest_palindrome(s):
        n = len(s)
        start = 0
        max_len = 1


        # Verificare palindrom pentru o subsecvență de lungime impară
    rez = P[maxpal]
        for i in range(1, n):
    ind = (maxpal - 1 - rez) // 2
            low = i - 1
    return rez, ind
            high = i + 1
            while low >= 0 and high < n and s[low] == s[high]:
                if high - low + 1 > max_len:
                    start = low
                    max_len = high - low + 1
                low -= 1
                high += 1


        # Verificare palindrom pentru o subsecvență de lungime pară
def verifica_restrictii(s):
        for i in range(1, n):
    if not s.isalpha() or not s.isupper() or len(s) > 100000:
            low = i - 1
        return False
            high = i
    return True
            while low >= 0 and high < n and s[low] == s[high]:
                if high - low + 1 > max_len:
                    start = low
                    max_len = high - low + 1
                low -= 1
                high += 1


         return max_len, s[start:start + max_len]
def main():
    file_in = "subsecventaIN.txt"
    file_out = "subsecventaOUT.txt"
    s = citire(file_in)
   
    if not verifica_restrictii(s):
         with open(file_out, 'w') as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return


     # Determinarea rezultatelor
     t = init(s)
     lungime_maxima, subsecventa_maxima = longest_palindrome(mesaj)
     rez, ind = manacher(t)
   
    with open(file_out, 'w') as fout:
        fout.write(f"{rez}\n")
        fout.write(f"{s[ind:ind + rez]}")


    # Scrierea rezultatelor în fișierul de ieșire
if __name__ == "__main__":
    with open("subsecventaout.txt", "w") as g:
    main()
        g.write(str(lungime_maxima) + "\n")
        g.write(subsecventa_maxima + "\n")


</syntaxhighlight>
</syntaxhighlight>

Latest revision as of 12:50, 18 May 2024

Cerința[edit | edit source]

O echipă de cercetători de la Agenţia Spaţială Europeană au recepţionat un mesaj provenit dintr-o

altă galaxie. În urma analizelor complexe efectuate asupra mesajului recepţionat, ei au descoperit că

mesajul conţine mai multe subsecvenţe neîntrerupte de caractere care sunt palindroame. Se ştie că o

secvenţă de caractere este un palindrom dacă prin citirea ei de la stânga la dreapta şi de la dreapta la

stânga se obţin aceleaşi caractere. Mesajul recepţionat este codificat doar cu literele mari A, B, …, Z

ale alfabetului englez şi nu conţine alte caractere.

Pentru analiza mesajului recepţionat cercetătorii au nevoie de un program care să determine subsecvenţa palindrom de lungime maximă. În cazul în care există mai multe subsecvenţe

care au aceeaşi lungime maximă, se va reţine subsecvenţa care apare prima dată

în scrierea mesajului, citit de la stânga spre dreapta.

De exemplu, pentru mesajul “CABABAD”, subsecvenţa palindrom cu lungimea maximă este “ABABA” şi are lungimea 5.

Date de intrare[edit | edit source]

În fișierul de intrare subsecventaIN.txt este scris şirul de caractere ale mesajului. Mesajul este format

doar din litere mari ale alfabetului englez şi are cel mult 100.000 de caractere.

Date de ieșire[edit | edit source]

Fișierul de ieșire subsecventaOUt.txt va conține pe prima linie un număr natural reprezentând lungimea

maximă a unei subsecvenţe palindrom, iar pe a doua linie se va scrie subsecvenţa

palindrom de lungime maximă care apare prima dată în mesaj. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări[edit | edit source]

  • Mesajul conţine doar litere mari şi are cel mult 100.000 de caractere.
  • Pentru 60% din teste numărul de caractere din fişierul de intrare este cel mult 1.000.

Exemplu 1:[edit | edit source]

subsecventaIN.txt

CABABAD

subsecventaOUT.txt

5
ABABA

Explicație[edit | edit source]

Cea mai lungă subsecvenţă palindrom are lungimea 5.

Exemplu 2:[edit | edit source]

subsecventaIN.txt

CABABADa

subsecventaOUT.txt

Datele nu corespund restrictiilor impuse


Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line="1"> def citire(file_in):

   with open(file_in, 'r') as fin:
       s = fin.read().strip()
   return s

def init(s):

   n = len(s)
   t = ['^']
   for char in s:
       t.append('#')
       t.append(char)
   t.append('#')
   t.append('\0')
   return .join(t)

def manacher(t):

   n = len(t)
   P = [0] * n
   C = R = 0
   maxpal = 1
   for i in range(1, n - 1):
       j = 2 * C - i
       if R > i:
           P[i] = min(R - i, P[j])
       while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
           P[i] += 1
       if i + P[i] > R:
           C = i
           R = i + P[i]
       if P[i] > P[maxpal]:
           maxpal = i
   rez = P[maxpal]
   ind = (maxpal - 1 - rez) // 2
   return rez, ind

def verifica_restrictii(s):

   if not s.isalpha() or not s.isupper() or len(s) > 100000:
       return False
   return True

def main():

   file_in = "subsecventaIN.txt"
   file_out = "subsecventaOUT.txt"
   s = citire(file_in)
   
   if not verifica_restrictii(s):
       with open(file_out, 'w') as fout:
           fout.write("Datele nu corespund restrictiilor impuse")
       return
   t = init(s)
   rez, ind = manacher(t)
   
   with open(file_out, 'w') as fout:
       fout.write(f"{rez}\n")
       fout.write(f"{s[ind:ind + rez]}")

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie[edit | edit source]

Cea mai lungă subsecvenţă palindrom are lungimea 5.
Există o singură subsecvenţă palindrom de lungime 5 în mesaj: ABABA.