Finding Maximal Quasiperiodicities in Strings (2000)
. Apostolico and Ehrenfeucht dened the notion of a maximal quasiperiodic substring and gave an algorithm that nds all maximal quasiperiodic substrings in a string of length n in time O(n log 2 n). In...
Optimal Purely Functional Priority Queues (1996)
Gerth St Lting, Gerth St��lting Brodal, Chris Okasaki
Brodal recently introduced the first implementation of imperative priority queues to support findMin, insert, and meld in O(1) worst-case time, and deleteMin in O(log n) worstcase time. These bounds...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth St Lting, Gerth St��lting Brodal, Jaikumar Radhakrishnan
The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...