== include(page="template/taskheader" task_id="anagrame") ==

Se dau două şiruri $S{~1~}$ si $S{~2~}$ formate doar cu litere mici. Numim subşir de lungime K al unui şir a un şir $a’=  a{~i{~1~}~},  a{~i{~2~}~},...,  a{~i{~K~}~}$, astfel încât să avem: $i{~1~} <  i{~2~} <  ...  <  i{~K~}$.

Se dau două şiruri $S{~1~}$ si $S{~2~}$ formate doar cu litere mici. Numim subşir de lungime $K$ al unui şir a un şir $a’=  a{~i{~1~}~},  a{~i{~2~}~},...,  a{~i{~K~}~}$, astfel încât să avem: $i{~1~} <  i{~2~} <  ...  <  i{~K~}$.

Să se determine lungimea maximă a unui subşir din $S{~1~}$, format prin concatenarea unor anagrame ale şirului $S{~2~}$. 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{~2~},..., 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.

Să se determine lungimea maximă a unui subşir din $S{~1~}$, format prin concatenarea unor anagrame ale şirului $S{~2~}$. Dintre toate subşirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un şir de lungime $n{~a~}$ se consideră mai mic lexicografic decât un şir de lungime $n{~b~}$ dacă există un indice {$1 &le; i &le; min(n{~a~}, n{~b~})$}, astfel încât $a{~1~}=b{~1~}, a{~2~}=b{~2~},..., 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.

h2. Date de intrare

h2. 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ă, iar dacă $P=2$, atunci pe prima linie se va scrie subşirul de lungime maximă cu proprietatea cerută şi minim lexicografic.

Î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.

h2. Restricţii

* $1 ≤ Lungime(S{~2~}) ≤ Lungime(S{~1~}) ≤ 100000$

* $1 ≤ Lungime(S{~2~}) ≤ Lungime(S{~1~}) ≤ 10^5^$

* Se garantează că cel puţin o anagramă a lui $S{~2~}$ apare în $S{~1~}$
h2. Exemplu

table(example). |_. anagrame.in |_. anagrame.out |_. explicatie |

table(example). |_. anagrame.in |_. anagrame.out |_. Explicatie |

| 1
  abbaaabababbaabaabba
  aba

| 15

| 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 ${*+ab+*}ba{*+aababa+*}b{*+baabaa+*}bba$ deci *$abaaabababaabaa$* este un subşir

  de lungime maximă, egală cu $15$, cu proprietatea cerută.

  de lungime maximă, egală cu $15$, cu proprietatea cerută. _Afisam *$5$* deoarece am concatenat *$5$* anagrame_

|
| 2
  abbaaabababbaabaabba