Suffix arrays – a contest approach

4 Conclusion 
During the contests it is more likely to use the O(n lg
2
n) solution, slower, but easier to implement. 
If possible, try not to use more than O(n) memory. The running time of the two solutions is scarcely 
different for a relatively small input string, and during a contest, the solution’s simplicity makes the 
implementation and debugging considerably easier. 
We draw the final conclusion that the suffix arrays are a very useful data structure, extremely easy 
to implement. Thus it’s not strange that during the last years many problems that were using it appeared in 
programming contests. For any questions or suggestions, please contact the authors using the following e-
mail addresses: 
[e-mail]
[e-mail]
16

---

References 
[1] Mark Nelson - Fast String Searching With Suffix Trees 
[2] Mircea Pa
ş
oi - Multe "smenuri" de programare in C/C++... si nu numai! (Many programming tricks in 
C/C++)– 
http://info.devnet.ro
[3] Emilian Miron – LCA – Lowest common ancestor – 
http://info.devnet.ro
[4] Michael A. Bender, Martin Farach–Colton - The LCA Problem Revisited
[5] Erik Demaine - MIT Advanced Data Structures – Lecture 11 - April 2, 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] Cormen, Leiserson, Rivest - Introduction to Algorithms 
[9] Dana Lica, Arbori de intervale (Segment Trees), GInfo 15/4 
[10]Negru
ş
eri Cosmin - C
ă
utari Ortogonale, Structuri de date 
ş
i aplica
ţ
ii (Orthogonal Searches, Data 
Structures and Applications), GInfo 15/5 
[9] 
www.boi2004.lv
[10] E. W. Dijkstra – Manuscripts Archive - 
http://www.cs.utexas.edu/users/EDW
17