Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems
Given two strings and and a set of strings , for each string , consider the unique substrings of that have as their prefix and 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 time algorithm for the counting problem, and an time algorithm for the listing problem, where refers to the number of strings being listed in total, and refers to the total length of the strings in . 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.