论文标题
更新动态后缀阵列的查询时间权衡
Update Query Time Trade-off for dynamic Suffix Arrays
论文作者
论文摘要
字符串s [1 ... n]的后缀阵列SA是一个阵列，包含词典顺序排序的所有后缀。后缀阵列是最著名的索引数据结构之一，它在许多字符串算法中充当关键工具。在本文中，我们提出了一个数据结构，用于维护动态字符串的后缀阵列。对于每$ 0 \ leq \ varepsilon \ leq 1 $，我们的数据结构报告了$ \ tilde {o}中的sa [i] sa [i]（n^{\ varepsilon}）$ time，并在$ \ tilde {o}中处理文本修改{o}（n^{1- \ varepsilon}）$ time。此外，我们的数据结构可以为报告ISA [i]的相同查询时间，ISA是S [1 ... N]的逆后缀阵列。我们的数据结构可用于构建基于后缀阵列和逆后缀阵列的静态字符串算法或数据结构的亚线性动态变体。
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 \leq \varepsilon \leq 1$, our data structure reports SA[i] in $\tilde{O}(n^{\varepsilon})$ time and handles text modification in $\tilde{O}(n^{1-\varepsilon})$ 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.
