Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems
share
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.
READ FULL TEXT