论文标题
基于十字树的线性算法，用于多个前缀，单个后缀计数和列表问题
Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems
论文作者
论文摘要
给定两个字符串$ t $和$ s $以及一套字符串$ p $，对于p $中的每个字符串$ p \，请考虑具有$ p $的唯一子字符串作为其前缀，而$ s $作为后缀。然后想到了两个问题。第一个问题是计数此类子字符串，第二个问题是列出所有此类子字符串的问题。在本文中，我们描述了两个问题的线性时间线性空间后缀基于树的算法。 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$.我们还考虑了问题的相反版本，其中一个前缀条件字符串和多个后缀条件字符串被提供，并类似地描述了线性时间，线性空间算法来求解它们。
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.
