A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time
A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time
复制标题
多对数时间内范围LCP查询的线性空间数据结构
DOI：
10.1007/978-3-319-94776
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Thankachan, S. V.
中科院分区：
文献类型：
--
作者：
Abedin, P.;Ganguly, A.;Hon, W. K.;Nekrich, Y.;Sadakane, K.;Shah, R.;Thankachan, S. V.
设T [1，n]是长度为n的文本，T [i，n]是从位置i开始的后缀。同样，对于任意两个字符串X和Y，让LCP（X，Y）表示它们的最长公共前缀。T的范围LCP为范围[α，β]，其中1≤ α< β≤ n为rlcp（α，β）= max {|LCP（T [i，n]，T [j，n]）||i ∈[α，β]} Amir et al. [2]引入了这个问题的索引版本，其中的任务是在T上构建一个数据结构，以便可以有效地报告任何查询范围[α，β]的rlcp（α，β）。他们提出了一个查询时间为O（log log n）的O（n log 1+ n）空间结构，以及一个查询时间为O（δ log log n）的线性空间结构（即O（n）个单词），其中δ= β− α+ 1是输入范围的长度，而δ> 0是一个任意小的常数。后来，Patil et al. [5]提出了另一种线性空间结构，其改进的查询时间为O（δ log δ）。这提出了一个有趣的问题，是否可以使用线性空间数据结构在多对数时间内回答rlcp（k，k）查询。本文提出了一种空间复杂度为O（n）的数据结构，其查询时间为O（log 1+ n），构造时间为O（n log n）。
Abstract Let T [1, n] be a text of length n and T [i, n] be the suffix starting at position i. Also, for any two strings X and Y, let LCP (X, Y) denote their longest common prefix. The range-LCP of T wrt a range [α, β], where 1≤ α< β≤ n is rlcp (α, β)= max{| LCP (T [i, n], T [j, n])|| i≠ j a n d i, j∈[α, β]} Amir et al.[2] introduced the indexing version of this problem, where the task is to build a data structure over T, so that rlcp (α, β) for any query range [α, β] can be reported efficiently. They proposed an O (n log 1+ ϵ n) space structure with query time O (log log n), and a linear space (ie, O (n) words) structure with query time O (δ log log n), where δ= β− α+ 1 is the length of the input range and ϵ> 0 is an arbitrarily small constant. Later, Patil et al.[5] proposed another linear space structure with an improved query time of O (δ log ϵ δ). This poses an interesting question, whether it is possible to answer rlcp (⋅,⋅) queries in poly-logarithmic time using a linear space data structure. In this paper, we settle this question by presenting an O (n) space data structure with query time O (log 1+ ϵ n) and construction time O (n log n).
登录
查看更多内容
DOI：
--
发表时间：
2013
期刊：
Annual Symposium on Combinatorial Pattern Matching
影响因子：
--
作者：
T. Gagie;Kalle Karhu;G. Navarro;S. Puglisi;Jouni Sirén
通讯作者：
Jouni Sirén
更快范围的 LCP 查询
DOI：
--
发表时间：
2013
期刊：
SPIRE
影响因子：
--
作者：
Manish Patil;Rahul Shah;Sharma V. Thankachan
通讯作者：
Sharma V. Thankachan
后缀树中的加权祖先
DOI：
--
发表时间：
2014
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Paweł Gawrychowski;Moshe Lewenstein;Patrick K. Nicholson
通讯作者：
Patrick K. Nicholson
DOI：
--
发表时间：
2005
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Graham Cormode;S. Muthukrishnan
通讯作者：
S. Muthukrishnan
范围最短唯一子字符串查询
DOI：
10.1007/978-3-030-32686-9_18
发表时间：
2019
期刊：
String Processing and Information Retrieval (SPIRE
影响因子：
--
作者：
Abedin, Paniz;Ganguly, Arnab;Pissis, Solon P.;Thankachan, Sharma V.
通讯作者：
Thankachan, Sharma V.