2024/11/18 by Waseem Akram, Akram, Waseem, Takuya Mieno +1
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #Advanced Database Systems and Queries #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.2411.12099
The string indexing problem is a fundamental computational problem with numerous applications, including information retrieval and bioinformatics. It aims to efficiently solve the pattern matching problem: given a text T of length n for preprocessing and a pattern P of length m as a query, the goal is to report all occurrences of P as substrings of T. Navarro and Thankachan [CPM 2015, Theor. Comput. Sci. 2016] introduced a variant of this problem called the gap-bounded consecutive occurrence query, which reports pairs of consecutive occurrences of P in T such that their gaps (i.e., the distances between them) lie within a query-specified range [g1, g2]. Recently, Bille et al. [FSTTCS 2020, Theor. Comput. Sci. 2022] proposed the top-k close consecutive occurrence query, which reports the k closest consecutive occurrences of P in T, sorted in non-decreasing order of distance. Both problems are optimally solved in query time with O(n log n)-space data structures. In this paper, we generalize these problems to the range query model, which focuses only on occurrences of P in a specified substring T[a.. b] of T. Our contributions are as follows: (1) We propose an O(n log2 n)-space data structure that answers the range top-k consecutive occurrence query in O(m + loglog n + k) time and can be built in O(n log3 n) time; and (2) We propose an O(n log2+ε n)-space data structure that answers the range gap-bounded consecutive occurrence query in O(m + loglog n + output) time and can be constructed in O(n log5/2n) time, where εis a positive constant and output denotes the number of outputs. As by-products, we present algorithms for geometric problems involving weighted horizontal segments in a 2D plane, which are of independent interest. Furthermore, we observe that consecutive occurrences are related to closed substrings of a string.