Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431042 | Journal of Discrete Algorithms | 2011 | 8 Pages |
Abstract
It is shown how to compute the lexicographically maximum suffix of a string of n⩾2n⩾2 characters over a totally ordered alphabet using at most (4/3)n−5/3(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)(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 >.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gianni Franceschini, Torben Hagerup,