14 citations · 17 across the 5 of their papers we have counts for
4 papers · 1 filter
Simplified Tight Bounds for Monotone Minimal Perfect Hashing
Dmitry Kosolobov
Given an increasing sequence of integers from a universe , the monotone minimal perfect hash function (MMPHF) for this sequence is a data structu…
Online Detection of Repetitions with Backtracking
Dmitry Kosolobov
In this paper we present two algorithms for the following problem: given a string and a rational , detect in the online fashion the earliest occurrence of a repetition of ex…
Online Square Detection
Dmitry Kosolobov
The online square detection problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. Recall that a square is a string…
Lempel-Ziv Factorization May Be Harder Than Computing All Runs
Dmitry Kosolobov
The complexity of computing the Lempel-Ziv factorization and the set of all runs (= maximal repetitions) is studied in the decision tree model of computation over ordered alphabet.…