# 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: (a) make_string -- add a string of
constant length, (b) concatenate -- concatenate two strings, (c) split -- split a
string into two at a given position, (d) compare -- find the lexicographical order
(less, equal, greater) between two strings, (e) LCP -- calculate the longest common
prefix of two strings. 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.