sal everybody. mor aici
Am folosit ca exemplu sursa mea de la password din arhiva pt aceasta problema, in care fac un fel de kmp (numai ca facand operatii doar pe substring cum ar veni..) - rez in O(n)
Scurta explicatie:
La fiecare moment am o pozitie din care banuiesc ca va incepe cea mai mica rotatie, si de la acea pozitie pana la pasul curent din sirul analizat (cel alcatuit din input+input) imi construiesc la fiecare pas cate putin vectorul overlap, sau pi, sau cum ii zice, de la kmp
.
Vad daca pot sa micsorez si mai mult acesta rotatie presupusa minima pastrand din ea doar cel mai lung sufix comun cu prefixul, peste care vin cu un caracter mai mic decat cel care urma imediat dupa prefix.
Problema e ca aici nu pot pastra decat anumite rotatii circulare care sunt conform regulii cu k, asa ca am zis ca daca gasesc o rotatie mai mica lexicografic decat cea presupusa, merg mai departe gasind si rotatii mai mici dar nu o salvez decat daca acea rotatie se poate obtine prin salturi de cate k.
Pare corect, totusi iau 0, numai WA for test in `seq 1 10` si nu stiu de ce. Pareri ?
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena