Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time

12/23/2021
by   Amihood Amir, et al.
0

The Suffix Array SA_S[1… n] of an n-length string S is a lexicographically sorted array of the suffixes of S. The suffix array is one of the most well known and widely used data structures in string algorithms. We present a data structure for maintaining a representation of the suffix array of a dynamic string which undergoes symbol substitutions, deletions, and insertions. For every string manipulation, our data structure can be updated in O(n^2/3) time (ignoring multiplicative polylogarithmic factors) with n being the current length of the string. For an input query i∈ [1… n], our data structure reports SA_S[i] in O(log^5(n)) time. We also present a faster data structure, with O(√(n)) update time (ignoring multiplicative polylogarithmic factors), for maintaining the Inverted Suffix Array of a dynamic string undergoing symbol substitutions updates. For an input query i∈ [1… n], our data structure reports the i'th entry in the inverted suffix array in O(log^4(n)) time. Our data structures can be used to obtain sub-linear dynamic algorithms for several classical string problems for which efficient dynamic solutions were not previously known.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset