Range Shortest Unique Substring Queries
Range Shortest Unique Substring Queries
复制标题
范围最短唯一子字符串查询
DOI：
10.1007/978-3-030-32686-9_18
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Thankachan, Sharma V.
中科院分区：
文献类型：
--
作者：
Abedin, Paniz;Ganguly, Arnab;Pissis, Solon P.;Thankachan, Sharma V.
设 是一个长度为 n 的字符串，并且是从位置 i 开始到位置 j 结束的子串。如果一个子串出现多次，则该子串是重复的；否则，它是 的唯一子串。重复和独特的子串在计算生物学和信息检索中引起了极大的兴趣。给定字符串作为输入，最短唯一子串问题是找到一个在其他地方没有出现的最短子串。在本文中，我们介绍了这个问题的范围变体，我们称之为范围最短唯一子串问题。任务是构建一个数据结构，有效地回答以下类型的在线查询。给定一个范围，返回恰好出现一次的最短子字符串。我们提出一个带有查询时间的单词数据结构，其中 是单词大小。我们的构造基于非平凡的简化，使我们能够应用最近引入的最佳几何数据结构 [Chan 等人。 ICLP 2018]。
Letbe a string of lengthnandbe the substring ofstarting at positioniand ending at positionj. A substringofis a repeat if it occurs more than once in; otherwise, it is a unique substring of. Repeats and unique substrings are of great interest in computational biology and in information retrieval. Given stringas input, theShortest Unique Substringproblem is to find a shortest substring ofthat does not occur elsewhere in. In this paper, we introduce the range variant of this problem, which we call theRange Shortest Unique Substringproblem. The task is to construct a data structure overanswering the following type of online queries efficiently. Given a range, return a shortest substringofwith exactly one occurrence in. We present an-word data structure withquery time, whereis the word size. Our construction is based on a non-trivial reduction allowing us to apply a recently introduced optimal geometric data structure [Chan et al. ICALP 2018].
登录
查看更多内容
多对数时间内范围LCP查询的线性空间数据结构
DOI：
10.1007/978-3-319-94776
发表时间：
2018
期刊：
International Computing and Combinatorics Conference
影响因子：
--
作者：
Abedin, P.;Ganguly, A.;Hon, W. K.;Nekrich, Y.;Sadakane, K.;Shah, R.;Thankachan, S. V.
通讯作者：
Thankachan, S. V.
游程编码字符串的最短唯一回文子串查询
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
Kiichi Watanabe
通讯作者：
Kiichi Watanabe
DOI：
--
发表时间：
2016
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
Arnab Ganguly;W. Hon;Rahul Shah;Sharma V. Thankachan
通讯作者：
Sharma V. Thankachan
CNEFinder：寻找基因组中保守的非编码元件
DOI：
--
发表时间：
2018
期刊：
Bioinform.
影响因子：
--
作者：
Lorraine A. K. Ayad;S. Pissis;D. Polychronopoulos
通讯作者：
D. Polychronopoulos
重新审视范围 LCP 查询
DOI：
--
发表时间：
2015
期刊：
SPIRE
影响因子：
--
作者：
A. Amir;Moshe Lewenstein;Sharma V. Thankachan
通讯作者：
Sharma V. Thankachan