Optimal dynamic strings

In this paper, we study the fundamental problem of maintaining a dynamic collection of strings under the following operations: <br />• make string – add a string of constant length, <br />• concat – concatenate two strings, <br />• split – split a string into two at a given position, <br />• compare – find the lexicographical order (less, equal, greater) between two strings, <br />• LCP – calculate the longest common prefix of two strings. <br />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 <em>n</em>) 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 Ω(log <em>n</em>) time; hence our implementation is optimal.