# Optimal Dynamic Strings

### Venue

SODA 2018 (to appear)

### Publication Year

2018

### Authors

Adam Karczmarz, Jakub Łącki, Paweł Gawrychowski, Piotr Sankowski, Tomasz Kociumaka

### BibTeX

## Abstract

In this paper we study the fundamental problem of maintaining a dynamic collection
of strings under the following operations: \begin{itemize} \item make_string -- add
a string of constant length, \item concatenate -- concatenate two strings, \item
split -- split a string into two at a given position, \item compare -- find the
lexicographical order (less, equal, greater) between two strings, \item LCP --
calculate the longest common prefix of two strings. \end{itemize} We develop a
generic framework for dynamizing the recompression method recently introduced by
Jeż [J. ACM 2016]. It allows us to present an efficient data structure for the
above problem, where an update requires only $O(\log n)$ worst-case time with high
probability, with $n$ being the total length of all strings in the collection, and
a query takes constant worst-case time. On the lower bound side, we prove that even
if the only possible query is checking equality of two strings, either updates or
queries must take amortized $\Omega(\log n)$ time; hence our implementation is
optimal.