Solutia problemei Balbaiala
Multumim lui 
Sa notam cu M marimea inputului.
Putem observa ca daca balbaiala de ordin x a sirului B apartine ca subsir in sirul A, atunci orice balbaiala a acestuia de ordin y va apartine ca subsir in sirul A, unde 0 ≤ y ≤ x. Asta inseamna ca exista un x astfel incat toate balbaielile de ordin mai mic sau egal cu x apar ca subsir, dar balbaiala de ordin x + 1 nu apare ca subsir. Deci putem cauta binar aceasta valoare.
Pentru 20 de puncte
Pentru 20 de puncte, putem construi de mana sirul de balbaiala x al sirului B si sa verificam in O(N) daca acesta apartine ca subsir.
Pentru 40 de puncte
Pentru 40 de puncte, aceasta solutie trebuie optimizata la verificarea proprietatii de subsir. Putem sa precalculam matricea nextpos[let][pos], care ne va spune pozitia minima > pos pe care apare litera let in sirul A. Spre exemplu, daca ma aflu pe pozitia pos in sirul A, pe care se afla litera A[pos], atunci cea mai din stanga pozitie > pos pe care se afla litera A[pos + 1] va fi exact nextpos[A[pos + 1]][pos]. In concluzie, putem lua fiecare litera din balbaiala de ordin x a sirului A si verifica daca pozitia pe care o cautam nu depaseste finalul sirului. Daca aceasta conditie este adevarata, sarim la pozitia dorita, schimbam litera si continuam. Daca nu, returnam fals. Aceasta solutie are complexitate de O(|B| * x) pentru fiecare x.
Aceasta solutie trebuie optimizata putin mai mult. Cum putem face asta? Folosind matricea calculata anterior noi putem sari din aparitie in aparitie a unei litere. Insa putem chiar mai bine - sa sarim din x in x aparitii!
Pentru 70-100 de puncte
Pentru 70 de puncte, vom grupa literele in 26 de "bucket-uri". In bucket-ul unei litere vom retine toate aparitiile acesteia in sirul A, in ordine crescatoare. Asta ne poate ajuta sa sarim de la o aparitie a unei litere la oricare alta. Vom retine o variabila pos, care ne va spune pozitia de dupa ultima litera luata. Cu alte cuvinte, pos ne va spune la fiecare moment de timp prefixul minim al lui A de care avem nevoie pentru ca prefixul deja procesat al lui B sa fie subsir in A. La inceput, pos va fi egal cu 0. Pentru fiecare litera din B vom cauta binar in bucket-ul corespunzator prima aparitie a ei de dupa pos, dupa care vom sari peste x aparitii ale acesteia si vom actualiza valoarea lui pos. Aceasta solutie are o complexitate teoretica de O(M * log2M), insa in practica, cu mici optimizari poate obtine 100 de puncte. Un avantaj al acestei solutii este memoria ocupata, noi nemaiavand nevoie de matricea nextpos.
Pentru 100 de puncte
In loc sa cautam binar in bucket-ul unei litere prima ei aparitie de dupa pos, putem sa precalculam pentru fiecare litera pe ce pozitie se afla in bucket-ul care o contine. Dupa ce trecem de la litera B[k] la litera B[k+1], actualizam valoarea lui pos. Apoi, folosindu-ne de matricea nextpos, calculata anterior, putem sa aflam prima pozitie a literei B[k + 1] de dupa pos, adica nextpos[B[k + 1]][pos]. Acum, stiind pozitia pe care se afla litera aceasta in bucket-ul ei, ne vom duce pe aceasta pozitie in bucket, vom lua urmatoarele x litere si vom actualiza valoarea lui pos. Aceasta solutie reduce complexitatea la O(M * logM), care intra lejer in restrictiile problemei.
