2043 - Subsecventa: Difference between revisions
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 = | |||
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. | ||
În fișierul de intrare | = Date de intrare = | ||
În fișierul de intrare <code>subsecventaIN.txt</code> este scris şirul de caractere ale mesajului. Mesajul este format | |||
Fișierul de ieșire | |||
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. | ||
*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 | ||
= | |||
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 = | |||
== | * Mesajul conţine doar litere mari şi are cel mult <code>100.000</code> de caractere. | ||
* Pentru 60% din teste numărul de caractere din fişierul de intrare este cel mult <code>1.000</code>. | |||
: | = Exemplu 1: = | ||
<code>subsecventaIN.txt</code> | |||
CABABAD | |||
<code>subsecventaOUT.txt</code> | |||
5 | |||
ABABA | |||
=== Explicație === | |||
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"> | ||
def citire(file_in): | |||
with open(file_in, 'r') as fin: | |||
with open( | 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]: | |||
if | 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> | </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.