![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Finding the Maximum Suffix with Fewer Comparisons
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,...
-
Article
Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves
We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e., preserving the original relative order of the equal elements), using O(1) auxiliary space a...
-
Chapter and Conference Paper
In-Place Suffix Sorting
Given string T = T[1,...,n], the suffix sorting problem is to lexicographically sort the suffixes T[i,...,n] for all i. This problem is central to the construction of suffix arrays and trees with many application...
-
Article
Optimal Implicit Dictionaries over Unbounded Universes
An array of n distinct keys can be sorted for logarithmic searching or can be organized as a heap for logarithmic updating, but it is unclear how to attain logarithmic time for both searching and updat...
-
Chapter and Conference Paper
Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves
We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e. preserving the original relative order of the equal elements), using O(1) auxiliary space and p...
-
Chapter and Conference Paper
Optimal In-place Sorting of Vectors and Records
We study the problem of determining the complexity of optimal comparison-based in-place sorting when the key length, k, is not a constant. We present the first algorithm for lexicographically sorting n keys in O(
-
Chapter and Conference Paper
A General Technique for Managing Strings in Comparison-Driven Data Structures
This paper presents a general technique for optimally transforming any dynamic data structure \(\mathcal{D}\) that oper...
-
Chapter and Conference Paper
Optimal Cache-Oblivious Implicit Dictionaries
We consider the issues of implicitness and cache-obliviousness in the classical dictionary problem for n distinct keys over an unbounded and ordered universe. One finding in this paper is that of closing the long...