Diferente pentru siruri-de-sufixe intre reviziile #40 si #41

Nu exista diferente intre titluri.

Diferente intre continut:

* _verificarea daca un string $W$ este substring al lui $A$_ - este suficienta parcurgerea nodurilor, incepand din radacina si urmarind muchiile etichetate corespunzator caracterelor din $W$ (complexitate $O(|W|)$)
* _cautarea celui mai lung prefix comun pentru doua sufixe ale lui $A$_ - se aleg nodurile $u$ si $v$ ale trie-ului corespunzatoare sfarsitului celor doua sufixe, iar prin aplicarea unui algoritm de gasire a LCA (Lowest Common Ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfarsitului prefixului cautat. De exemplu, pentru $abac$ si $ac$ se gasesc nodurile $5$ si $6$. Cel mai apropiat stramos comun al lor este $2$, de unde rezulta prefixul $a$. Autorii va recomanda articolul ^{'[2]':siruri-de-sufixe#bibliografie}^ pentru o rezolvare in $O(sqrt(n))$, '[3]':siruri-de-sufixe#bibliografie pentru o prezentare accesibila a unei rezolvari in $O(log n)$ sau $O(1)$, si articolul '[4]':siruri-de-sufixe#bibliografie pentru un algoritm "state of the art".
* _cautarea celui mai lung prefix comun pentru doua sufixe ale lui $A$_ - se aleg nodurile $u$ si $v$ ale trie-ului corespunzatoare sfarsitului celor doua sufixe, iar prin aplicarea unui algoritm de gasire a LCA (Lowest Common Ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfarsitului prefixului cautat. De exemplu, pentru $abac$ si $ac$ se gasesc nodurile $5$ si $6$. Cel mai apropiat stramos comun al lor este $2$, de unde rezulta prefixul $a$. Autorii va recomanda articolul '[2]':siruri-de-sufixe#bibliografie pentru o rezolvare in $O(sqrt(n))$, '[3]':siruri-de-sufixe#bibliografie pentru o prezentare accesibila a unei rezolvari in $O(log n)$ sau $O(1)$, si articolul '[4]':siruri-de-sufixe#bibliografie pentru un algoritm "state of the art".
* _gasirea celui de-al $k$-lea sufix in ordine lexicografica_ - (complexitate $O(n)$, cu o preprocesare corespunzatoare). De exemplu al $3$-lea sufix al sirului $abac$ este reprezentat in trie-ul nostru de a $3$-a frunza.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.