14 citations · 16 across the 4 of their papers we have counts for
4 papers
Faster Lightweight Lempel-Ziv Parsing
Dmitry Kosolobov
We present an algorithm that computes the Lempel-Ziv decomposition in time and bits of space, where is a constant rational parameter, …
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.…