It is shown how to compute the lexicographically maximum suffix of a string of n≥2 characters over a totally ordered alphabet using at most (4/3)n-5/3 three-way character comparisons. The best previous bound, which has stood unchallenged for more than 25 years, is (3/2)n-O(1) comparisons. We also prove an interesting property of an algorithm for computing the maximum suffix both with respect to a total order < and with respect to its inverse order >. © 2011 Elsevier B.V. © 2011 Elsevier B.V. All rights reserved.
Finding the maximum suffix with fewer comparisons / Franceschini, Gianni; Torben, Hagerup. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - STAMPA. - 9:3(2011), pp. 279-286. [10.1016/j.jda.2011.03.008]
Finding the maximum suffix with fewer comparisons
FRANCESCHINI, GIANNI;
2011
Abstract
It is shown how to compute the lexicographically maximum suffix of a string of n≥2 characters over a totally ordered alphabet using at most (4/3)n-5/3 three-way character comparisons. The best previous bound, which has stood unchallenged for more than 25 years, is (3/2)n-O(1) comparisons. We also prove an interesting property of an algorithm for computing the maximum suffix both with respect to a total order < and with respect to its inverse order >. © 2011 Elsevier B.V. © 2011 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
