2026-08-17T00:16:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13407 2024-03-14T07:16:37Z ddc:004 open_access

Update Query Time Trade-Off for Dynamic Suffix Arrays Amir, Amihood Boneh, Itai String Algorithms Dynamic Algorithms Suffix Array Inverse Suffix Array The Suffix Array SA(S) of a string S[1 … n] is an array containing all the suffixes of S sorted by lexicographic order. The suffix array is one of the most well known indexing data structures, and it functions as a key tool in many string algorithms. In this paper, we present a data structure for maintaining the Suffix Array of a dynamic string. For every 1 ≤ k ≤ n, our data structure reports SA[i] in 𝒪̃(n/k) time and handles text modification in 𝒪̃(k) time. Additionally, our data structure enables the same query time for reporting iSA[i], with iSA being the Inverse Suffix Array of S[1 … n]. Our data structure can be used to construct sub-linear dynamic variants of static strings algorithms or data structures that are based on the Suffix Array and the Inverse Suffix Array. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amihood Amir and Itai Boneh 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.63 urn:nbn:de:0030-drops-134070 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.63 eng https://creativecommons.org/licenses/by/3.0/legalcode