Enunțul problemei interesant, de clasa a 10-a, dată în 2016 la OJI, se găsește pe PbInfo și InfoArena.

Rezumat interesant

Se dă o mulțime s ce conține n șiruri de caractere formate doar din litere mici. Un șir de caractere se consideră interesant dacă nu există niciun alt șir în mulțimea s care să-l conțină ca subșir (nu subsecvență). Prima cerință este să determinăm cel mai lung șir din mulțimea dată. Dacă există mai multe șiruri de lungime maximă, trebuie afișat cel minim din punct de vedere lexicografic. A doua cerință este să afișăm șirurile interesante (în ordinea în care apar în fișierul de intrare), împreună cu numărul lor.

Soluție interesant

Pentru a reține șirurile de caractere convenabil în raport cu cerințele problemei, am definit un struct Str. Acesta conține câmpurile id (poziția string-ului din timpul citirii), lg (lungimea string-ului) și str (șirul în sine). Am supraîncărcat operatorul < pentru acest tip de date și i-am scris două criterii de sortare. Primul (operator<) sortează șirurile crescător din punct de vedere al lungimii, iar în caz de egalitate, descrescător lexicografic. Al doilea (cmp) le sortează crescător după id.

După citirea datelor, am sortat vectorul de șiruri după primul criteriu, și pentru fiecare string am căutat un posibil string care să-l conțină ca subșir. Pentru asta, am parcurs vectorul în ordine inversă, pentru că șansele sunt mai mari ca un string mai lung să-l conțină ca subșir pe celălalt. Am marcat în vectorul no pentru fiecare string dacă este interesant sau nu, iar la final am sortat vectorul după al doilea criteriu pentru a-i restabili ordinea inițială și a afișa soluția. Pentru a doua cerință era de ajuns să afișăm ultimul element al vectorului după prima sortare.

Sursă C++ interesant

Dacă ai vreo nedumerire cu privire la problema interesant, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!