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 hot id. 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 >.
Finding the Maximum Suffix with Fewer Comparisons / Franceschini, Gianni; Torben, Hagerup. - STAMPA. - 6078:(2010), pp. 323-334. (Intervento presentato al convegno 7th International Conference on Algorithms and Complexity tenutosi a Rome; Italy) [10.1007/978-3-642-13073-1_29].
Finding the Maximum Suffix with Fewer Comparisons
FRANCESCHINI, GIANNI;
2010
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 hot id. 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 >.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
