Faster Range LCP Queries
Faster Range LCP Queries
复制标题
更快范围的 LCP 查询
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Sharma V. Thankachan
中科院分区：
文献类型：
--
作者：
Manish Patil;Rahul Shah;Sharma V. Thankachan
范围LCP（最长的常见前缀）是经典LCP问题的扩展，定义如下：预处理A string s [1 ... n]，以便max a，b∈{i ... j} lcp（s a a a a a ，s b）可以对输入i，j∈[1，n]有效计算，其中lcp（s a，s b）是S从位置a和b开始的S后缀最长常见前缀的长度。在本文中，我们用O（（J -i）1/2log e（j -i））查询时间描述了线性空间数据结构，其中E> 0是任何常数。 - i）loglogn）Amir等人的查询时间解决方案。
Range LCP (longest common prefix) is an extension of the classical LCP problem and is defined as follows: Preprocess a string S[1...n] so that max a,b ∈ {i...j }LCP(S a , S b ) can be computed efficiently for the input i, j ∈ [1, n], where LCP(S a , S b ) is the length of the longest common prefix of the suffixes of S starting at locations a and b. In this paper, we describe a linear space data structure with O((j - i)1/2log e (j - i)) query time, where e > 0 is any constant. This improves the linear space and O((j - i)loglogn) query time solution by Amir et. al. [ISAAC, 2011].