$suf1 = aab aaaab$
$pre = aab$
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.
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
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.
h2. 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_, GInfo 15/5 (Mai 2005), Editura Agora Media;
11. 'BOI 2004':http://www.boi2004.lv/;
