Update Query Time Trade-off for dynamic Suffix Arrays

07/13/2020
by   Amihood Amir, et al.
0

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 0 ≤ε≤ 1, our data structure reports SA[i] in Õ(n^ε) time and handles text modification in Õ(n^1-ε) 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset