| 1 |
Optimal Dynamic Strings ...
|
|
|
|
Abstract:
In this paper we study the fundamental problem of maintaining a dynamic collection of strings under the following operations: concat - concatenates two strings, split - splits a string into two at a given position, compare - finds the lexicographical order (less, equal, greater) between two strings, LCP - calculates the longest common prefix of two strings. We present an efficient data structure for this 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 take amortized $Ω(\log n)$ time; hence our implementation is optimal. Such operations can be used as a basic building block to solve other string problems. We provide two examples. First, we can augment our data structure to provide pattern matching queries that may locate ...
|
|
Keyword:
68P05, 68W32; Data Structures and Algorithms cs.DS; F.2.2; FOS Computer and information sciences
|
|
URL: https://dx.doi.org/10.48550/arxiv.1511.02612
https://arxiv.org/abs/1511.02612
|
|
BASE
|
|
Hide details
|
|
|
|
|
