Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.13162 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913468018327552 |
|---|---|
| author | Lipták, Zsuzsanna Masillo, Francesco Navarro, Gonzalo |
| author_facet | Lipták, Zsuzsanna Masillo, Francesco Navarro, Gonzalo |
| contents | We consider the problem of maintaining a collection of strings while efficiently supporting splits and concatenations on them, as well as comparing two substrings, and computing the longest common prefix between two suffixes. This problem can be solved in optimal time $\mathcal{O}(\log N)$ whp for the updates and $\mathcal{O}(1)$ worst-case time for the queries, where $N$ is the total collection size [Gawrychowski et al., SODA 2018]. We present here a much simpler solution based on a forest of enhanced splay trees (FeST), where both the updates and the substring comparison take $\mathcal{O}(\log n)$ amortized time, $n$ being the lengths of the strings involved. The longest common prefix of length $\ell$ is computed in $\mathcal{O}(\log n + \log^2\ell)$ amortized time. Our query results are correct whp. Our simpler solution enables other more general updates in $\mathcal{O}(\log n)$ amortized time, such as reversing a substring and/or mapping its symbols. We can also regard substrings as circular or as their omega extension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_13162 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Textbook Solution for Dynamic Strings Lipták, Zsuzsanna Masillo, Francesco Navarro, Gonzalo Data Structures and Algorithms We consider the problem of maintaining a collection of strings while efficiently supporting splits and concatenations on them, as well as comparing two substrings, and computing the longest common prefix between two suffixes. This problem can be solved in optimal time $\mathcal{O}(\log N)$ whp for the updates and $\mathcal{O}(1)$ worst-case time for the queries, where $N$ is the total collection size [Gawrychowski et al., SODA 2018]. We present here a much simpler solution based on a forest of enhanced splay trees (FeST), where both the updates and the substring comparison take $\mathcal{O}(\log n)$ amortized time, $n$ being the lengths of the strings involved. The longest common prefix of length $\ell$ is computed in $\mathcal{O}(\log n + \log^2\ell)$ amortized time. Our query results are correct whp. Our simpler solution enables other more general updates in $\mathcal{O}(\log n)$ amortized time, such as reversing a substring and/or mapping its symbols. We can also regard substrings as circular or as their omega extension. |
| title | A Textbook Solution for Dynamic Strings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.13162 |