Multumim lui ==user(user="Matteoalexandru" type="tiny")== pentru editorial!

_In curand..._

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.
 
h2. 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.
 
h2. 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!
 
h2. 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 * log^2^M)$, 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$.
 
h2. 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.