Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems

Abstract

Given two strings $T$ and $S$ and a set of strings $P$, for each string $p\in 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.

16 pages, 5 figures