.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » string

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
string


Timp maxim de executie/test:
0.6 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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 în sirul S2, daca lungimea sirului S2 (egala cu numarul de caractere ale sirului) este mai mare sau egala decât a sirului S1 si exista o pozitie k în sirul S2, astfel încât 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 decât lungimea sirului S2, iar X[i] reprezinta al i-lea caracter din sirul X. De exemplu, sirul 'abba' este inclus în sirul 'babbaba', dar nu este inclus în sirul 'ababab'.

Cerinta

Determinati cel mai scurt sir format numai din caractere din alfabetul considerat, care sa nu fie inclus în sirul S.

Date de intrare

Pe prima linie a fisierului de intrare string.in se afla numarul întreg N, reprezentând numarul de caractere ale sirului S. Pe urmatoarea linie se afla cele N caractere, în ordinea pozitiei lor în sir.

Date de iesire

Pe prima linie a fisierului de iesire string.out veti afisa numarul întreg L, reprezentând lungimea minima a unui sir care nu este inclus în 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
  • L > 0

Exemplu

string.in string.out
11
aabaaabbbab
4
aaaa

Mugurel Andreica
Universitatea Politehnica Bucuresti

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor