| Fişierul intrare/ieşire: | anagrame.in, anagrame.out | Sursă | ONI 2018, clasa a 10-a, ziua 1 |
| Autor | Ionel-Vasile Pit-Rada | Adăugată de |  Laura Georgescu •laurageorgescu |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | anagrame.out | Explicatie |
|---|---|---|
| 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ă. |
