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' = a
i1
, a
i2
,…, a
iK
astfel încât să avem: i1 < i2 < ... < iK
.
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 a
1
=b
1
, a
2
=b
1
, …, a
i-1
=b
i-1
și a
i
<b
i
. 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 anagrame3.in
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 anagrame3.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ă, 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 înS1
Exemplul 1:
anagrame3.in
1 abbaaabababbaabaabba aba
anagrame3.out
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:
anagrame3.in
2 abbaaabababbaabaabba aba
anagrame3.out
abaaabaabaabaab
Explicație
Se observă că subșirul verifică proprietatea cerută.