Efficient data structures for range shortest unique substring queries

Paniz Abedin, Arnab Ganguly, Solon P. Pissis*, Sharma V. Thankachan

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Let T[1, n] be a string of length n and T[i, j] be the substring of T starting at position i and ending at position j. A substring T[i, j] of T is a repeat if it occurs more than once in T; otherwise, it is a unique substring of T. Repeats and unique substrings are of great interest in computational biology and information retrieval. Given string T as input, the Shortest Unique Substring problem is to find a shortest substring of T that does not occur elsewhere in T. In this paper, we introduce the range variant of this problem, which we call the Range Shortest Unique Substring problem. The task is to construct a data structure over T answering the following type of online queries efficiently. Given a range [α, β], return a shortest substring T[i, j] of T with exactly one occurrence in [α, β]. We present an O(n log n)-word data structure with O(logw n) query time, where w = Ω(log n) is the word size. Our construction is based on a non-trivial reduction allowing for us to apply a recently introduced optimal geometric data structure [Chan et al., ICALP 2018]. Additionally, we present an O(n)-word data structure with O( n logɛ n) query time, where ɛ > 0 is an arbitrarily small constant. The latter data structure relies heavily on another geometric data structure [Nekrich and Navarro, SWAT 2012].

Original languageEnglish
Article number276
Pages (from-to)1-9
Number of pages9
JournalAlgorithms
Volume13
Issue number11
Early online date30 Oct 2020
DOIs
Publication statusPublished - Nov 2020

Bibliographical note

Special Issue: Combinatorial Methods for String Processing.

Keywords

  • Geometric data structures
  • Heavy-light decomposition
  • Range queries
  • Shortest unique substring
  • Suffix tree

Fingerprint

Dive into the research topics of 'Efficient data structures for range shortest unique substring queries<sup>†</sup>'. Together they form a unique fingerprint.

Cite this