18 citations · 54 across the 16 of their papers we have counts for
Showing 2014 · cs.DSShow all
3 papers · 2 filters
cs.DS2014
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…
cs.DS2014★ 1 cited
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…
cs.DS2014★ 14 cited
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.…