2022/03/31 by Laurentius Leonard, Ken Tanaka, Leonard, Laurentius +1
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 #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.2203.16908
openalex publication_date 2022/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two strings T and S and a set of strings P, for each string p ∈ P, consider the unique substrings of T that have p as their prefix and S as their suffix. Two problems then come to mind; the first problem being the counting of such substrings, and the second problem being the problem of listing all such substrings. In this paper, we describe linear-time, linear-space suffix tree-based algorithms for both problems. More specifically, we describe an O(|T| + |P|) time algorithm for the counting problem, and an O(|T| + |P| + #(ans)) time algorithm for the listing problem, where #(ans) refers to the number of strings being listed in total, and |P| refers to the total length of the strings in P. We also consider the reversed version of the problems, where one prefix condition string and multiple suffix condition strings are given instead, and similarly describe linear-time, linear-space algorithms to solve them.