2019/05/30 by Takuya Mieno, Dominik Köppl, Mieno, Takuya +9
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.1905.12854
openalex publication_date 2019/05/30 · openalex created_date 2020/09/21 · openalex updated_date 2026/07/28
Given a string T of length n, a substring u = T[i..j] of T is called a shortest unique substring (SUS) for an interval [s,t] if (a) u occurs exactly once in T, (b) u contains the interval [s,t] (i.e. i ≤ s ≤ t ≤ j), and (c) every substring v of T with |v| < |u| containing [s,t] occurs at least twice in T. Given a query interval [s, t] ⊂ [1, n], the interval SUS problem is to output all the SUSs for the interval [s,t]. In this article, we propose a 4n + o(n) bits data structure answering an interval SUS query in output-sensitive O(occ) time, where occ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for s = t. Here, we propose a \lceil (log23 + 1)n \rceil + o(n) bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of T.