Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyOptimal dynamic strings
| dc.abstract.en | 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. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Stany Zjednoczone |
| dc.conference.datefinish | 2018-01-10 |
| dc.conference.datestart | 2018-01-07 |
| dc.conference.place | New Orleans |
| dc.conference.series | ACM/SIAM Symposium on Discrete Algorithms |
| dc.conference.series | ACM/SIAM Symposium on Discrete Algorithms |
| dc.conference.seriesshortcut | SODA |
| dc.conference.shortcut | SODA 2018 |
| dc.conference.weblink | https://archive.siam.org/meetings/da18/ |
| dc.contributor.author | Łącki, Jakub |
| dc.contributor.author | Kociumaka, Tomasz |
| dc.contributor.author | Karczmarz, Adam |
| dc.contributor.author | Sankowski, Piotr |
| dc.contributor.author | Gawrychowski, Paweł |
| dc.date.accessioned | 2024-01-25T15:58:33Z |
| dc.date.available | 2024-01-25T15:58:33Z |
| dc.date.issued | 2018 |
| dc.description.finance | Nie dotyczy |
| dc.identifier.doi | 10.1137/1.9781611975031.99 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/114994 |
| dc.identifier.weblink | https://doi.org/10.1137/1.9781611975031.99 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 1509-1528 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.title | Optimal dynamic strings |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |