Computing minimal and maximal suffixes of a substring
Computing minimal and maximal suffixes of a substring
复制标题
计算子字符串的最小和最大后缀
DOI：
10.1016/j.tcs.2015.08.023
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Tatiana Starikovskaya
中科院分区：
文献类型：
--
作者：
M. Babenko;Paweł Gawrychowski;Tomasz Kociumaka;Ignat I. Kolesnichenko;Tatiana Starikovskaya
我们考虑了计算长度为n的较长文本的子串的最大和最小非空后缀的问题.对于最小后缀问题，我们证明了对于每一个τ，1≤τ≤n，存在一个查询时间为O(τ)和预处理时间为O(n≤τ≤n/τ)的线性空间数据结构.作为一个示例应用，我们证明了该数据结构可以用于计算文本的任何子串的林登分解在O(kτ)时间内，其中k是分解中的不同因子的个数。对于最大后缀问题，我们给出了一个查询时间为O(1)，处理时间为O(N)的线性空间结构。换句话说，我们同时实现了最优查询时间和最优构造时间。
We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length n. For the minimal suffix problem we show that for every τ, 1≤ τ≤ log n, there exists a linear-space data structure with O (τ) query time and O (n log n/τ) preprocessing time. As a sample application, we show that this data structure can be used to compute the Lyndon decomposition of any substring of the text in O (k τ) time, where k is the number of distinct factors in the decomposition. For the maximal suffix problem, we give a linear-space structure with O (1) query time and O (n) preprocessing time. In other words, we simultaneously achieve both the optimal query time and the optimal construction time.