Fişierul intrare/ieşire:anagrame.in, anagrame.outSursăONI 2018, clasa a 10-a, ziua 1
AutorIonel-Vasile Pit-RadaAdăugată delaurageorgescuLaura Georgescu laurageorgescu
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Anagrame

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 < i2 < ... < iK.

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 1 ≤ i ≤ min(na, nb), astfel încât a1=b1, a2=b2,..., 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

În fişierul anagrame.in, 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 anagrame.out, dacă P=1, atunci pe prima linie se va scrie un număr natural reprezentând lungimea maximă a unui şir cu proprietatea cerută (exprimat in numarul de anagrame - vezi exemplul), iar dacă P=2, atunci pe prima linie se va scrie subşirul de lungime maximă cu proprietatea cerută şi minim lexicografic.

Restricţii

  • 1 ≤ Lungime(S2) ≤ Lungime(S1) ≤ 105
  • Se garantează că cel puţin o anagramă a lui S2 apare în S1

Exemplu

anagrame.inanagrame.outExplicatie
1
abbaaabababbaabaabba
aba
5
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ă. Afisam 5 deoarece am concatenat 5 anagrame
2
abbaaabababbaabaabba
aba
abaaabaabaabaab
Se observă că subşirul verifică proprietatea cerută.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?