== code(c) |
n <- lungime(A)
pentru i <- 0, n-1

	P(0, i) <- pozitia lui Ai in sirul ordonat al caracterelor lui A
sfarsit pentru

	P(0, i) <- pozitia in sirul ordonat al caracterelor lui A a lui Ai

cnt <- 1
pentru k <- 1, [log2 n] (marginit superior)
	pentru i <- 0, n-1
		L(i) <- (P(k-1, i), P(k-1, i+cnt), i)

        sfarsit pentru

	sorteaza L

	calculeaza P(k, i), i = 0, n-1

	calculeaza P(k, i), i = 0,n-1

	cnt <- 2 * cnt

sfarsit pentru

==
De remarcat ca nu este neparat necesara o anumita numerotare a substringurilor, atat timp cat intre ele este pastrata o relatie de ordine valida. In vederea atingerii complexitatii $O(n lg n)$ pentru sortare se recomanda folosirea metodei _radix sort_ (de doua ori sortare prin numarare), aceasta avand complexitate $O(n)$. Insa, pentru usurarea implementarii, se poate folosi functia $sort()$ din STL (Standard Template Library, o librarie ce contine unele structuri de date si algoritmi in limbajul C++). Desi complexitatea va creste la $O(n lg^2^ n)$ in cazul cel mai defavorabil, implementarea devine simtitor mai simpla, iar in practica diferentele sunt abia sesizabile pentru siruri cu lungime mai mica decat $100 000$.

h3. Solutie:

De obicei, in probleme unde apare rotatia unui sir dat, putem sa ne folosim de trucul de a concatena sirului de caractere acelasi sir pentru a simplifica problema. Dupa aceasta transformare problema ne cere subsecventa lexicografica minima de lungime n a noului sir. Ordinea subsecventelor de lungime n ale unui sir este egala cu ordinea sufixelor determinate de subsecventele date, deci ne putem folosi de siruri de sufixe pentru a rezolva aceasta problema.

De obicei, in probleme unde apare rotatia unui sir dat, putem sa ne folosim de trucul de a concatena sirului de caractere acelasi sir pentru a simplifica problema. Dupa aceasta transformare problema ne cere subsecventa lexicografica minima de lungime n a noului sir. Ordinea subsecventelor de lungime n ale unui sir este egala cu ordinea sufixelor determinate de subsecventele date, deci ne putem folosi de arborii de sufixe pentru a rezolva aceasta problema.

O problema asemanatoare a fost propusa de unul dintre autori la concursul Bursele Agora, editia 2003-2004, care se putea rezolva pe aceiasi idee. Implementarea trebuia facuta atent pentru solutia oficiala era o rezolvare eficienta ce nu folosea aceasta structura de date.
h3. *Problema 2*: _sir_ (baraj 2004)
Se considera un sir $c{~1~}c{~2~}...c{~n~}$ format din $n$ $(1 ≤ 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.

_Nota suplimentara_: fie $X$ si $Y$ doua siruri oarecare, iar "$o$" operatia de concatenare. In aceasta problema se va considera ca $X > X o Y$.

_Nota suplimentara_: fie $X$ si $Y$ doua siruri oarecare, iar $o$ operatia de concatenare. In aceasta problema se va considera ca $X > X o Y$.

h3. Solutie: