D. Kosolobov

activity

20132022

most citedLZ-End Parsing in Compressed Space

18 citations · 54 across the 16 of their papers we have counts for

collaborators

Showing 2016Show all

3 papers · 1 filter

cs.DS2016

Tight Lower Bounds for the Longest Common Extension Problem

Dmitry Kosolobov

The longest common extension problem is to preprocess a given string of length $n$ into a data structure that uses $S (n)$ bits on top of the input and answers in $T (n)$ time the qu…

cs.DS2016★ 18 cited

LZ-End Parsing in Compressed Space

Dominik Kempa, Dmitry Kosolobov

We present an algorithm that constructs the LZ-End parsing (a variation of LZ77) of a given string of length $n$ in $O (n lo g ℓ)$ expected time and $O (z + ℓ)$ space, where $z$ …

cs.DS2016

Detecting One-variable Patterns

Dmitry Kosolobov, Florin Manea, Dirk Nowotka

Given a pattern $p = s_{1} x_{1} s_{2} x_{2} \dots s_{r - 1} x_{r - 1} s_{r}$ such that $x_{1}, x_{2}, \dots, x_{r - 1} \in {x, x_{\leftarrow}}$ , where $x$ is a variable and $\overset{{}_{\lefta…