Deterministic Sparse Suffix Sorting in the Restore Model
Deterministic Sparse Suffix Sorting in the Restore Model
复制标题
DOI：
10.1145/3398681
复制
发表时间：
2020-09-01
影响因子：
1.3
通讯作者：
Koppl, Dominik
中科院分区：
文献类型：
--
作者：
Fischer, Johannes;Tomohiro, I;Koppl, Dominik
给定一个长度为n的文本T，在T的空间为n的前提下，提出了一个确定性的在线算法，在O（c root lg n + mlgmlgnlg * n）时间内，O（m）字空间内计算T的稀疏后缀数组和稀疏最长公共前缀数组，其中m
Given a text T of length n, we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in O(c root lg n + m lg m lg n lg* n) time with O(m) words of space under the premise that the space of T is rewritable, where m