Zmicala Narcis: Pagină nouă: Se dau două șiruri '''S1''' si '''S2''' formate doar cu litere mici. Numim subșir de lungime '''K''' al unui șir a un șir '''a' = ai1, ai2,…, aiK''' astfel încât să avem: '''i1''' == Cerința == Să se determine lungimea maximă a unui subșir din '''S1''', format prin concatenarea unor anagrame ale șirului '''S2'''. Dintre toate subșirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un șir de lungime na se consideră mai mic lexi...

2024-01-03T14:58:02Z

Pagină nouă: Se dau două șiruri '''S1''' si '''S2''' formate doar cu litere mici. Numim subșir de lungime '''K''' al unui șir a un șir '''a' = ai1, ai2,…, aiK''' astfel încât să avem: '''i1''' == Cerința == Să se determine lungimea maximă a unui subșir din '''S1''', format prin concatenarea unor anagrame ale șirului '''S2'''. Dintre toate subșirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un șir de lungime na se consideră mai mic lexi...

New page

Se dau două șiruri '''S1''' si '''S2''' formate doar cu litere mici. Numim subșir de lungime '''K''' al unui șir a un șir '''a' = ai1, ai2,…, aiK''' astfel încât să avem: '''i1'''
== Cerința ==
Să se determine lungimea maximă a unui subșir din '''S1''', format prin concatenarea unor anagrame ale șirului '''S2'''. Dintre toate subșirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un șir de lungime na se consideră mai mic lexicografic decât un șir de lungime nb dacă există un indice i, astfel încât '''a1=b1, a2=b1, …, ai-1=bi-1''' și '''ai<bi'''. Un șir '''a''' este anagrama unui șir '''b''' dacă sortându-le crescător pe fiecare se obțin două șiruri identice.
== Date de intrare ==
Fișierul de intrare '''anagrame3in.txt''' conține pe prima linie se află un număr natural '''P'''. Pe linia a doua se află șirul '''S1''', iar pe a treia linie se află șirul '''S2'''.
== Date de ieșire ==
În fișierul '''anagrame3out.txt''', dacă '''P = 1''', atunci pe prima linie se va scrie un număr natural reprezentând lungimea maximă a unui șir cu proprietatea cerută, iar dacă '''P = 2''', atunci pe prima linie se va scrie subșirul de lungime maximă cu proprietatea cerută și minim lexicografic.
== Restricții și precizări ==
* '''1 ≤ Lungime(S2) ≤ Lungime(S1) ≤ 100 000'''
* Se garantează că cel puțin o anagramă a lui '''S2''' apare în '''S1'''
== Exemplul 1 ==
; anagrame3in.txt
: 1
: abbaaabababbaabaabba
: aba
; anagrame3out.txt
: Datele introduse corespund restricțiilor impuse.
: 15
== Explicație ==
Deoarece a apare de '''11''' ori, '''S2''' poate să apară de cel mult '''5''' ori. Se observă subșirul format cu litere îngroșate și subliniate '''abbaaabababbaabaabba''' deci '''abaaabababaabaa''' este un subșir de lungime maximă, egală cu '''15''', cu proprietatea cerută.
== Exemplul 2 ==
; anagrame3in.txt
: 2
: abbaaabababbaabaabba
: aba
: anagrame3.out
: Datele de intrare corespund restricțiilor impuse.
: abaaabaabaabaab
== Explicație ==
Se observă că subșirul verifică proprietatea cerută.
== Exemplul 3 ==
; anagrame3in.txt
: 2
: abbaaabababbaabaabba
: abababababababababab
; anagrame3.out
: Datele de intrare nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 2464 - anagrame3
from collections import Counter

def validare(sirul1, sirul2): # functia de validare a datelor de intrare
if not (1 <= len(sirul2) <= len(sirul1) <= 100000):
raise ValueError("Datele introduse nu corespund restrictiilor impuse.")

def gaseste_subsir(sirul1, sirul2, p1): # functia de rezolvare
count_sir2 = Counter(sirul2)
subsiruri = []
for i in range(len(sirul1) - len(sirul2) + 1):
if Counter(sirul1[i:i + len(sirul2)]) == count_sir2:
subsiruri.append(sirul1[i:i + len(sirul2)])
subsiruri.sort()
if p1 == 1:
return len(subsiruri[-1])
elif p1 == 2:
return subsiruri[0]

if __name__ == '__main__':
fisier_intrare = open("anagrame3in.txt", "r") # declararea fisierelor
fisier_iesire = open("anagrame3out.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
p = int(fisier_intrare.readline())
sir1 = fisier_intrare.readline().strip()
sir2 = fisier_intrare.readline().strip()

validare(sir1, sir2) # apelul functiei de validare
rezultat = gaseste_subsir(sir1, sir2, p) # apelul functiei de rezolvare
fisier_iesire.write(str(rezultat))

except ValueError:
fisier_iesire.write("Datele introduse nu corespund restrictiilor impuse.")

</syntaxhighlight>

2464 - anagrame3 - Revision history