Google Research

Optimal Dynamic Strings

  • Adam Karczmarz
  • Jakub Łącki
  • Paweł Gawrychowski
  • Piotr Sankowski
  • Tomasz Kociumaka
SODA 2018 (to appear)

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work