Pagini recente » Istoria paginii utilizator/andreivoaga | Cod sursa (job #789025) | Cod sursa (job #2010350) | Cod sursa (job #1220156) | Diferente pentru rotatie-lexicografic-minima intre reviziile 27 si 28
Nu exista diferente intre titluri.
Diferente intre continut:
* $*S[min+l] = S[p+l]* ->$ se va incrementa variabila $l$ cu o unitate deoarece inca o pereche de caractere se potrivesc
* $*S[min+l] < S[p+l]* ->$ putem trage imediat concluzia ca $R ~min~ < R ~p~$ , iar mai mult, din faptul ca primele $l$ caractere se potrivesc putem spune ca $R ~min+i~ < R ~p+i~$ pentru $0 <= i <= l$; cum $R ~min~$ era rotatia "candidata" la solutia finala dintre $R ~0~, R ~1~, ... R ~p-1~$ si este mai mica ca $R ~p~$, iar pentru orice $R ~p+i~ (1 <= i <= l)$ exista $R ~min+i~ < R ~p+i~$, despre care se stie ca nu poate fi solutia finala, $R ~min~$ va repezenta in continuare rotatia candidata la solutie dintre $R ~0~, R ~1~, ... R ~p-1~, R ~p~, R ~p+1~, ... R ~p+l~$. Asadar $p$ va deveni $p+l+1$, iar $l$ va deveni $0$ (deoarece nu se cunosc inca informatii despre $R ~min~$ si $R ~p+l+1~$)
* $*S[min+l] > S[p+l]* ->$ asemanator cu cazul anterior putem concluziona ca $R ~min+i~ > R ~p+i~$ pentru $0 <= i <=
l$; asadar putem face doua observatii:
* $*S[min+l] > S[p+l]* ->$ asemanator cu cazul anterior putem concluziona ca $R ~min+i~ > R ~p+i~$ pentru $0 ≤ i ≤ l$; asadar putem face doua observatii:
$1) R ~min+i~ (0 <= i <= l)$ nu poate candida la solutie, si cum se stia dinainte ca nici $R ~0~, R ~1~, ... R ~min-1~$ nu pot, primul candidat posibil este $R ~min+l+1~$;
$2) Cum R ~min~$ era candidatul pana in prezent, iar $R ~p~ < R ~min~$, din $R ~0~, R ~1~, ... R ~p~$ singurul candidat posibil este $R ~p~$.
Variabila $min$ va deveni $max(min+l+1, p)$, $p$ va deveni $max(min+l+1, p)+1$, iar $l$ va fi egal cu $0$.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.