Kss

Pentru a rezolva aceasta problema vom incerca o abordare de genul urmator. Daca am putea raspunde la intrebarea: "Avand un prefix oarecare, cate subsiruri distincte incep cu acest prefix?", putem incerca sa cautam fiecare litera pe rand din solutie pana cand gasim intregul sir cerut. Construim o dinamica din[ i ] = numarul de subsiruri distincte care incep de pe pozitia i si contin litera de pe pozitia i. Ca sa rezolvam aceasta dinamica mai intai definim next[ c ][ i ] = prima pozitie dupa i pe care apare caracterul c (daca c apare fix pe pozitia i atunci next[ c ][ i ] = i). Vom calcula dinamica de la pozitia N spre pozitia 1, iar recurenta este: din[ i ] = 1 + suma dupa c = a,z din din[ next[ c ][ i + 1 ] ]. Luam doar prima aparatie a fiecarui caracter pentru ca subsirurile sunt distincte dupa valoare, si nu dupa pozitiile pe care apar caracterele in sirul initial; luam in calcul si cazul cand subsirul contine doar caracterul curent. Avand aceasta dinamica putem incepe sa cautam solutia, pentru ca putem raspunde la intrebarea intiala astfel: daca avem un prefix p, il potrivim ca subsir peste sirul S astfel incat ultimul caracter al lui p apare cat mai repede in S (de exemplu pentru p = a b si S = c a b b vom potrivi c a b b si nu c a b b ). Fie q aceasta pozitie a ultimul caracter din p. Numarul de subsiruri care incep cu acest prefix p este din[ q ] si se observa usor de ce.

In continuare voi explica mai detaliat cum gasim propriu-zis solutia. Dorim sa gasim al K-lea subsir. Sa presupunem mai intai ca sirul nostru incepe cu litera a. Determinam acel q (am explicat mai sus ce reprezinta). Daca cumva din[q] < K atunci inseamna ca solutia nu va incepe cu a ci cu o litera mai mare (lexicografic) pentru ca nu sunt suficiente subsiruri care incep cu a. Scadem din K, din[q] si incercam urmatoarea litera b pentru ca aplicam acelasi rationament (incercam sa gasim al K-din[q]-lea subsir care nu incepe cu a ). Cand din[q] >= K inseamna ca litera curenta este cea buna si atunci trebuie sa gasim urmatoarea (la acest pas trebuie sa scadem 1 din K pentru ca sirul care se termina fix cu litera curenta apare lexicografic inaintea celor ce vor urma, mai lungi). Pentru urmatoarea litera aplicam acelasi rationament decat ca trebuie sa avem grija ca acum inceputul solutiei este un prefix si nu doar o litera. Ne oprim atunci cand K-ul ramas devine 0 (adica tocmai am pus ultima litera).

Solutia aceasta are o complexitate N * sigma pe fiecare test ( sigma este numarul de caractere din alfabet).