* 'Introducere':siruri-de-sufixe#introducere
* 'Ce sunt sirurile de sufixe (suffix arrays)?':siruri-de-sufixe#prezentare
* 'Cum construim un sir de sufixe?':siruri-de-sufixe#constructie
* 'Calcularea celui mai lung prefix comun (LCP)':siruri-de-sufixe#lcp
* 'Calcularea celui mai lung prefix comun @(LCP)@':siruri-de-sufixe#lcp
* 'Cautarea':siruri-de-sufixe#cautare
* 'Probleme de concurs':siruri-de-sufixe#probleme
* 'Concluzii':siruri-de-sufixe#concluzii
* 'Bibliografie':siruri-de-sufixe#bibliografie
h2(#introducere). Introducere
Deoarece sirul de sufixe ne ofera ordinea sufixelor lui $A$, cautarea unui string $W$ in $A$ se poate face simplu cu o cautare binara. Deoarece compararea se face in $O(|W|)$, cautarea va avea complexitatea $O(|W| lg n)$. Lucrarea [6] ofera structurii de date si algoritmului de cautare cateva rafinamente ce permit reducerea timpului la $O(|W| + lg n)$, dar autorii nu considera ca acestea sunt folositoare in concursurile de programare.
h2(#probleme). Probleme de concurs
h2(#probleme). Probleme de concurs *TODO*
Autorii au incercat sa adune cat mai multe probleme ce pot fi rezolvate cu ajutorul sirurilor de sufixe. Parcurgerea tuturor problemelor la prima citire, ar putea fi greoaie pentru un cititor care a avut primul contact cu aceasta structura de date citind acest articol. Pentru a usura lectura problemele sunt asezate intr-o ordine crescatoare a dificultatilor.
Observam astfel ca daca sirul $S$ se potriveste cu sufixul sau pe cel putin $k * |pre|$ caractere, atunci $S$ are un prefix de lungime $(k+1) * |pre|$ care este periodic. Folosindu-ne de structura de date $siruri de sufixe$, putem determina pentru fiecare sufix potrivirea maxima cu sirul initial. Daca al $i$-lea sufix se potiveste cu sirul pe primele $k * (i-1)$ pozitii, atunci putem actualiza informatia care indica daca prefixele de dimensiune $j * (i-1)$ (unde $2 ≤ j ≤ k$) sunt periodice. Pentru fiecare sufix $S$, actualizarea tuturor informatiilor are ordinul de complexitate $O(n / (i-1))$. Astfel, ordinul de complexitate al algoritmului de rezolvare a acestei probleme este $O(n log n)$. Trebuie remarcat faptul ca putem obtine o rezolvare in timp $O(n)$ folosind o idee similara si algoritmul $KMP$, dar prezentarea acestei rezolvari depaseste scopul acestui articol.
h2. Concluzii
h2(#concluzii). Concluzii
Mentionam ca in timpul concursurilor autorii prefera solutiile ale caror ordine de complexitate sunt $O(n log^2^ n)$, mai lente, dar mai usor de implementat, si care folosesc un spatiu de memorie de ordinul $O(n)$. Din punctul de vedere al timpului real de executie, cele doua tipuri de solutii vor fi comparabile, iar in concurs simplitatea solutiei usureaza foarte mult implementarea si depanarea. Din cele prezentate putem concluziona ca sirurile de sufixe sunt o structura de date usor de implementat si foarte utila. In ultimii ani apar la concursuri multe probleme care necesita cunoasterea acestora. Mai putem observa si faptul ca polonezii propun probleme destul de grele la olimpiade. Speram ca acest articol va va fi de folos si ca de acum inainte sirurile de sufixe vor fi la indemana oricui are nevoie de ele pentru a le folosi intr-un concurs de informatica.
Mentionam ca in timpul concursurilor autorii prefera solutiile ale caror ordine de complexitate sunt $O(n log^2^ n)$, mai lente, dar mai usor de implementat, si care folosesc un spatiu de memorie de ordinul $O(n)$. Din punctul de vedere al timpului real de executie, cele doua tipuri de solutii vor fi comparabile, iar in concurs simplitatea solutiei usureaza foarte mult implementarea si depanarea. Din cele prezentate putem concluziona ca sirurile de sufixe sunt o structura de date usor de implementat si foarte utila. In ultimii ani apar la concursuri tot mai multe probleme care necesita cunoasterea acestora. Mai putem observa si faptul ca polonezii propun probleme destul de grele la olimpiade. Speram ca acest articol va va fi de folos si ca de acum inainte sirurile de sufixe vor fi la indemana oricui are nevoie de ele pentru a le folosi intr-un concurs de informatica.
h2. Bibliografie
h2(#bibliografie). Bibliografie
1. Mark Nelson, _Fast String Searching With Suffix Trees_;
2. Mircea Pasoi, '_Multe "smenuri" de programare in C/C++... si nu numai!_':http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai;
3. Emilian Miron, '_LCA - Lowest common ancestor_':http://infoarena.ro/lca-lowest-common-ancestor;
4. Michael A. Bender, Martin Farach-Colton, _The LCA Problem Revisited_;
5. Erik Demaine, _MIT Advanced Data Structures, Lecture 11, April 2nd, 2003_;
6. Udi Mamber, Gene Myers, _Suffix arrays: A new method for on-line string searches_;
7. Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch, _Replacing suffix trees with enhanced suffix arrays_, Journal of Discrete Algorithms 2, 2004;
8. Thomas Cormen, Charles Leiserson, Ronald Rivest, '_Introducere in algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm, Editura Computer Libris Agora, 2000;
9. Dana Lica, '_Arbori de intervale_':http://infoarena.ro/arbori-de-intervale;
10. Negruseri Cosmin, '_Cautari ortogonale_':http://infoarena.ro/cautari-ortogonale, GInfo 15/5 (Mai 2005), Editura Agora Media;
11. 'BOI 2004':http://www.boi2004.lv/;
# Mark Nelson, _Fast string searching with suffix trees_
# Mircea Pasoi, '_Multe "smenuri" de programare in C/C++... si nu numai!_':multe-smenuri-de-programare-in-cc-si-nu-numai
# Emilian Miron, '_LCA - Lowest common ancestor_':lca-lowest-common-ancestor
# Michael A. Bender, Martin Farach-Colton, _The LCA Problem Revisited_
# Erik Demaine, _MIT Advanced Data Structures, Lecture 11, April 2nd, 2003_
# Udi Manber, Gene Myers, '_Suffix arrays: A new method for on-line string searches_':http://webglimpse.net/pubs/suffix.pdf
# Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch, _Replacing suffix trees with enhanced suffix arrays_, Journal of Discrete Algorithms 2, 2004
# Thomas Cormen, Charles Leiserson, Ronald Rivest, '_Introducere in algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm, Editura Computer Libris Agora, 2000
# Dana Lica, '_Arbori de intervale_':arbori-de-intervale
# Cosmin Negruseri, '_Cautari ortogonale_':cautari-ortogonale, GInfo 15/5 (Mai 2005), Editura Agora Media
# 'BOI 2004':http://www.boi2004.lv/
