Finding the maximum suffix with fewer comparisons |
| |
Authors: | Gianni Franceschini Torben Hagerup |
| |
Affiliation: | aDipartimento di Informatica, Università “La Sapienza” di Roma, Italy;bInstitut für Informatik, Universität Augsburg, 86135 Augsburg, Germany |
| |
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 >. |
| |
Keywords: | String algorithms Maximum suffix Character comparisons |
本文献已被 ScienceDirect 等数据库收录! |