h2. Calcularea celui mai lung prefix comun (LCP)
Se dau doua sufixe ale unui string $A$. Se cere calcularea celui mai lung prefix comun al lor. Am aratat ca un arbore de sufixe poate realiza aceasta in timp $O(1)$ cu o preprocesare corespunzatoare. Sa vedem daca un sir de sufixe poate atinge aceeasi performanta.

Fie cele doua sufixe $A{~i~}$ si $A{~j~}$. Folosind matricea $P$, putem itera descrescator de la cel mai mare $k$ pana la $0$ si verifica daca $A{~i~}^k^$ = $A{~j~}^k^$. Daca cele doua prefixe sunt egale, am gasit un prefix comun de lungime $2k$. Nu ne ramane decat sa actualizam $i$ si $j$, incrementandu-le cu $2k$ si sa verificam in continuare daca mai gasim prefixe comune.

Fie cele doua sufixe $A{~i~}$ si $A{~j~}$. Folosind matricea $P$, putem itera descrescator de la cel mai mare $k$ pana la $0$ si verifica daca $A{~i~}^k^$ = $A{~j~}^k^$. Daca cele doua prefixe sunt egale, am gasit un prefix comun de lungime $2^k^$. Nu ne ramane decat sa actualizam $i$ si $j$, incrementandu-le cu $2^k^$ si sa verificam in continuare daca mai gasim prefixe comune.

Codul functiei care calculeaza _LCP_ este foarte simplu:
== code(cpp) |

h3. Solutie:

Avand sufixele textului sortate, iteram cu o variabila $i$ de la $0$ la $N – K$ si calculam cel mai lung prefix comun intre sufixul $i$ si sufixul $i + K – 1$. Prefixul maxim determinat in cursul acestei parcurgeri reprezinta solutia problemei.

Avand sufixele textului sortate, iteram cu o variabila $i$ de la $0$ la $N-K$ si calculam cel mai lung prefix comun intre sufixul $i$ si sufixul $i+K-1$. Prefixul maxim determinat in cursul acestei parcurgeri reprezinta solutia problemei.

h3. *Problema 4*: _ghicit_ (baraj 2003)