Vom incerca acum sa obtinem un algoritm de complexitate liniara folosind alte idei de rezolvare. Algoritmul pe care il vom propune in continuare functioneaza ca si algoritmul trivial mentionat mai sus, anume parcurgand rotatiile succesiv. La fiecare pas se vor pastra trei variabile min, p, l cu semnificatia ca rotatiile R ~0~, R ~1~, ... R ~p-1~ au fost parcurse pana acum, iar R ~min~ este o rotatie dintre acestea care ar putea fi cea lexicografic minima (toate celelalte din cele parcurse sigur nu pot fi solutia finala). De asemenea, variabila l va semnifica ca primele l caractere din R ~min~ sunt egale cu primele l caractere din R ~p~, R ~p~ fiind urmatoarea rotatie ce va fi procesata. Cunoscand aceste informatii, la fiecare pas se va compara al l+1-lea caracter din R ~min~ (S[min+l]) cu al l+1-lea din R ~p~ (S[p+l]), iar in functie de rezultat se va lua o decizie:
* 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 <=
* *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:
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.
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.
Un aspect al acestui algoritm care ar putea parea "misterios" este motivul pentru care complexitatea este liniara. Vom considera T = min+p+l si putem observa ca dupa fiecare comparatie T creste cu cel putin o unitate. Cum niciuna din cele trei variabile nu poate depasi valoarea N, numarul de iteratii este proportional cu N (se poate arata ca nu va depasi 2*N-3), de unde si complexitatea O(N).
==code(c) |
min <- 0; p <- 1; l <- 1;
cat timp (p < N) AND (min+l+1 < N) executa
daca S[min+l] = S[p+l] atunci l <- l+1;
daca S[min+l] < S[p+l] atunci p <- p+l+1; l <- 0;
daca S[min+l] > S[p+l] atunci min <- max(min+l+1, p); p <- min+1; l <- 0;
sfarsit cat timp
scrie min
==
Vom simula algoritmul pentru sirul S = ("m", "i", "s", "s", "i", "s", "s", "i", "p", "p", "i").
min = 0 p = 1 l = 0 ; S[min+l] = "m" > S[p+l] = "i" ->
min = 1 p = 2 l = 0 ; S[min+l] = "i" < S[p+l] = "s" ->
min = 1 p = 3 l = 0 ; S[min+l] = "i" < S[p+l] = "s" ->
min = 1 p = 4 l = 0 ; S[min+l] = "i" = S[p+l] = "i" ->
min = 1 p = 4 l = 1 ; S[min+l] = "s" = S[p+l] = "s" ->
min = 1 p = 4 l = 2 ; S[min+l] = "s" = S[p+l] = "s" ->
min = 1 p = 4 l = 3 ; S[min+l] = "i" = S[p+l] = "i" ->
min = 1 p = 4 l = 4 ; S[min+l] = "s" > S[p+l] = "p" ->
min = 6 p = 7 l = 0 ; S[min+l] = "s" > S[p+l] = "i" ->
min = 7 p = 8 l = 0 ; S[min+l] = "i" < S[p+l] = "p" ->
min = 7 p = 9 l = 0 ; S[min+l] = "i" < S[p+l] = "p" ->
min = 7 p = 10 l = 0 ; S[min+l] = "i" = S[p+l] = "i" ->
min = 7 p = 10 l = 1 ; S[min+l] = "p" > S[p+l] = "m" ->
min = 10
h2. Aplicatii
*Problema 1 ("acm.sgu.ru":http://acm.sgu.ru, "problema 232":http://acm.sgu.ru/problem.php?contest=0&problem=232)*
Se dau doua numere naturale N<=150000 si K<=10^9^ si un vector de cifre D[0...N-1]. Se va considera un sir A de numere reale cu partea intreaga 0, iar partea fractionara a elementului A[i] va fi sirul infinit format din D[(i+0*K) mod N], D[(i+1*K) mod N], D[(i+2*K) mod N], etc. Spre exemplu, pentru N = 3, K = 2 si D = '194' se obtine:
A[1] = 0.1491491491...
A[2] = 0.9149149149...
A[3] = 0.4914914914...
Sa se gaseasca cel mai mare element ca valoare din sirul A, si sa se tipareasca primele N zecimale ale sale.
*Problema 2 (Selectia lotului international, 2004)*
Se considera un sir c ~1~ c ~2~ ...c ~n~ format din n <= 30.000 caractere din multimea {A, B}. Concatenam sirul cu el insusi si obtinem un sir de lungime 2n. Pentru un indice k (1<=k<=2n) consideram subsecventele de lungime cel mult n, care se termina pe pozitia k, iar dintre acestea fie s(k) subsecventa cea mai mica in ordine lexicografica. Determinati indicele k pentru care s(k) are lungimea cea mai mare.
