106 Prefix

[•Florian]

Am scos O(N), fara KMP. Initial mi s-a parut bulaneala, si nu ma asteptam sa ia 100 (in ciuda faptului ca nu am gasit teste pe care sa nu mearga). Dar acum cred ca este corecta solutia. In mare, o stare este definita de i, L si bst[ i ] . i e pozitia curenta, L este lungimea perioadei (acel P din enunt), iar bst[ i ] este nr de caractere care au fost puse la sfarsitul prefixului 1...i, din cele L ale perioadei. Si fac asa: daca s[ i ] == s[ i - L ], atunci bst[ i ] = bst[ i - 1 ] + 1, altfel bst[ i ] = 0 si L = i. De asemenea, daca cumva bst[ i ] == L, atunci fac bst [ i ] = 0. A mai rezolvat cineva asemanator ? 

[•Cristian1997]

Imi poate explica cineva de ce aceasta sursa ia TLE pe testul 8?
Multumesc

[•Djok]

Adauga ios_base::sync_with_stdio(0);
mai jos de deschiderea fișierelor.

[•Cristian1997]

N-a mers: http://www.infoarena.ro/job_detail/1722780