. Comp, we compute the array P Comp of size |P airs|, such that, for Comp[P airs[l].?]] (where P airs[l].? is the second member of the pair of integers in position l of P airs). Fourth. Using P airs and P Comp, we select the (k ? n < )-th smallest key suffix s x and all the key suffixes equal to s x according to the total order ? (where n < is the number of suffixes of S that are lexicographically smaller than each suffix in R, known since Sec, Third. By scanning P airs and Comp at the same time

]. A. Aggarwal and J. Vitter, The input/output complexity of sorting and related problems, Communications of ACM, 1988.
DOI : 10.1145/48529.48535
URL : https://hal.archives-ouvertes.fr/inria-00075827

M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, vol.7, issue.4, pp.448-61, 1973.
DOI : 10.1016/S0022-0000(73)80033-9

D. Dobkin and J. I. Munro, Optimal Time Minimal Space Selection Algorithms, Journal of the ACM, vol.28, issue.3, pp.454-461, 1981.
DOI : 10.1145/322261.322264

M. Farach, Optimal suffix tree construction with large alphabets, Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.137-143, 1997.
DOI : 10.1109/SFCS.1997.646102
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4336

M. Farach, P. Ferragina, and S. Muthukrishnan, Overcoming the memory bottleneck in suffix tree construction, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), 1998.
DOI : 10.1109/SFCS.1998.743441

G. Franceschini and S. Muthukrishnan, Optimal suffix selection, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , STOC '07, 2007.
DOI : 10.1145/1250790.1250840
URL : https://hal.archives-ouvertes.fr/inria-00359742

M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, Cache-oblivious algorithms, Proc. 40th Annual Symp. on Foundations of Computer Science (FOCS 1999), pp.285-297, 1999.

Z. Galil, Optimal parallel algorithms for string matching, Information and Control, vol.67, issue.1-3, pp.144-157, 1985.
DOI : 10.1016/S0019-9958(85)80031-0

E. M. Mccreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM, vol.23, issue.2, pp.262-272, 1976.
DOI : 10.1145/321941.321946

J. Vitter, Algorithms and Data Structures for External Memory, Foundations and Trends?? in Theoretical Computer Science, vol.2, issue.4, 2007.
DOI : 10.1561/0400000014

P. Weiner, Linear pattern matching algorithms, 14th Annual Symposium on Switching and Automata Theory (swat 1973), 1973.
DOI : 10.1109/SWAT.1973.13
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.474.9582