Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | string.in, string.out | Sursă | .campion 2003 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
String
Se considera alfabetul format numai din literele mici a si b si un sir S format numai din caractere din acest alfabet. Pe acest alfabet, se defineste relatia de incluziune, astfel: un sir S1 este inclus in sirul S2, daca lungimea sirului S2 (egala cu numarul de caractere ale sirului) este mai mare sau egala decat a sirului S1 si exista o pozitie k in sirul S2, astfel incat S2, k = S1,1, S2,k+1 = S1,2, ... , S2,k+L-1 = S1,L, unde L este lungimea sirului S1, k+L-1 este mai mic sau egal decat lungimea sirului S2 , iar Xi reprezinta al i-lea caracter din sirul X. De exemplu, sirul abba este inclus in sirul babbaba, dar nu este inclus in sirul ababab.
Cerinta
Determinati cel mai scurt sir format numai din caractere din alfabetul considerat, care sa nu fie inclus in sirul S.
Date de intrare
Pe prima linie a fisierului de intrare string.in se afla numarul intreg N, reprezentand numarul de caractere ale sirului S. Pe urmatoarea linie se afla cele N caractere, in ordinea pozitiei lor in sir.
Date de iesire
Pe prima linie a fisierului de iesire string.out veti afisa numarul intreg L, reprezentand lungimea minima a unui sir care nu este inclus in sirul S. Pe a doua linie veti afisa un astfel de sir. Daca exista mai multe solutii, puteti afisa oricare dintre ele.
Restrictii
- 1 ≤ N ≤ 500.000
- 0 < L
Exemplu
string.in | string.out |
---|---|
11 aabaaabbbab | |
4 aaaa |