如何修改后缀数组以搜索多个字符串？
How to Modify a Suffix Array to search multiple strings?
我最近一直在更新我的算法知识，并一直在阅读后缀数组。我读过的每一篇文章都将它们定义为单个搜索字符串的后缀数组，但有些文章提到它 'trivial' 可以概括为整个搜索字符串列表，但我看不出如何。
假设我正在尝试对单词列表实施简单的子字符串搜索，并希望 return 匹配给定子字符串的单词列表。天真的方法似乎是在我的列表中的单词之间插入字典结束字符“$”，将它们连接在一起，并从结果中生成一个后缀树。但这似乎会生成大量不相关的条目。如果我创建一个 'banana$muffin' 的源字符串，那么我最终会为 'ana$muffin' 生成我永远不会使用的后缀。
对于如何正确执行此操作的任何提示，或者更好的是，提供指向处理这种情况的一些算法文本的指针，我将不胜感激。
在 Suffix-Arrays 中你通常不使用字符串，只使用一个字符串。这将是几个字符串的连接版本，带有一些结束标记（每个字符串都有一个不同的结束标记）。对于后缀数组，您使用指针（或数组索引）来引用后缀（只需要第一个 token/character 的位置）。
所以 space 需要的是数组 + 每个后缀的指针。 （这只是一个非常简单的实现，您应该做更多，以获得更高的性能）。
在那种情况下，您可以优化后缀的排序算法，因为您只需要对指针引用的那些后缀进行排序，直到结束标记。 endtoken 后面的所有内容都不需要在排序算法中使用。
在阅读了 Dan Gusfield 的 关于字符串、树和序列的算法 的大部分内容后，答案似乎很明确。
如果您从多字符串后缀树开始，其中一种标准转换算法仍然有效。但是，您最终得到的不是一个整数数组，而是一个列表数组。每个列表包含一对或多对字符串标识符和该字符串中的起始偏移量。
生成的结构仍然有用，但不如普通后缀数组有效。
来自爱荷华州立大学，摘自Prefix.pdf：
Suffix trees and suffix arrays can be generalized to multiple strings.
The generalized suffix tree of a set of strings S = {s1, s2, . . . ,
sk}, denoted GST(S) or simply GST, is a compacted trie of all suffixes
of each string in S. We assume that the unique termination character $
is appended to the end of each string. A leaf label now consists of a
pair of integers (i, j), where i denotes the suffix is from string si
and j denotes the starting position of the suffix in si . Similarly,
an edge label in a GST is a substring of one of the strings. An edge
label is represented by a triplet of integers (i, j, l), where i
denotes the string number, and j and l denote the starting and ending
positions of the substring in si . For convenience of understanding,
we will continue to show the actual edge labels. Note that two strings
may have identical suffixes. This is compensated by allowing leaves in
the tree to have multiple labels. If a leaf is multiply labelled, each
suffix should come from a different string. If N is the total number
of characters (including the $ in each string) of all strings in S,
the GST has at most N leaf nodes and takes up O(N) space. The
generalized suffix array of S, denoted GSA(S) or simply GSA, is a
lexicographically sorted array of all suffixes of each string in S.
Each suffix is represented by an integer pair (i, j) denoting suffix
starting from position j in si . If suffixes from different strings
are identical, they occupy consecutive positions in the GSA. For
convenience, we make an exception for the suffix $ by listing it only
once, though it occurs in each string. The GST and GSA of strings
apple and maple are shown in Figure 1.2.
这里有一篇关于构造 GSA 的算法的文章：
Generalized enhanced suffix array construction in external memory
我最近一直在更新我的算法知识，并一直在阅读后缀数组。我读过的每一篇文章都将它们定义为单个搜索字符串的后缀数组，但有些文章提到它 'trivial' 可以概括为整个搜索字符串列表，但我看不出如何。
假设我正在尝试对单词列表实施简单的子字符串搜索，并希望 return 匹配给定子字符串的单词列表。天真的方法似乎是在我的列表中的单词之间插入字典结束字符“$”，将它们连接在一起，并从结果中生成一个后缀树。但这似乎会生成大量不相关的条目。如果我创建一个 'banana$muffin' 的源字符串，那么我最终会为 'ana$muffin' 生成我永远不会使用的后缀。
对于如何正确执行此操作的任何提示，或者更好的是，提供指向处理这种情况的一些算法文本的指针，我将不胜感激。
在 Suffix-Arrays 中你通常不使用字符串，只使用一个字符串。这将是几个字符串的连接版本，带有一些结束标记（每个字符串都有一个不同的结束标记）。对于后缀数组，您使用指针（或数组索引）来引用后缀（只需要第一个 token/character 的位置）。 所以 space 需要的是数组 + 每个后缀的指针。 （这只是一个非常简单的实现，您应该做更多，以获得更高的性能）。
在那种情况下，您可以优化后缀的排序算法，因为您只需要对指针引用的那些后缀进行排序，直到结束标记。 endtoken 后面的所有内容都不需要在排序算法中使用。
在阅读了 Dan Gusfield 的 关于字符串、树和序列的算法 的大部分内容后，答案似乎很明确。
如果您从多字符串后缀树开始，其中一种标准转换算法仍然有效。但是，您最终得到的不是一个整数数组，而是一个列表数组。每个列表包含一对或多对字符串标识符和该字符串中的起始偏移量。
生成的结构仍然有用，但不如普通后缀数组有效。
来自爱荷华州立大学，摘自Prefix.pdf：
Suffix trees and suffix arrays can be generalized to multiple strings. The generalized suffix tree of a set of strings S = {s1, s2, . . . , sk}, denoted GST(S) or simply GST, is a compacted trie of all suffixes of each string in S. We assume that the unique termination character $ is appended to the end of each string. A leaf label now consists of a pair of integers (i, j), where i denotes the suffix is from string si and j denotes the starting position of the suffix in si . Similarly, an edge label in a GST is a substring of one of the strings. An edge label is represented by a triplet of integers (i, j, l), where i denotes the string number, and j and l denote the starting and ending positions of the substring in si . For convenience of understanding, we will continue to show the actual edge labels. Note that two strings may have identical suffixes. This is compensated by allowing leaves in the tree to have multiple labels. If a leaf is multiply labelled, each suffix should come from a different string. If N is the total number of characters (including the $ in each string) of all strings in S, the GST has at most N leaf nodes and takes up O(N) space. The generalized suffix array of S, denoted GSA(S) or simply GSA, is a lexicographically sorted array of all suffixes of each string in S. Each suffix is represented by an integer pair (i, j) denoting suffix starting from position j in si . If suffixes from different strings are identical, they occupy consecutive positions in the GSA. For convenience, we make an exception for the suffix $ by listing it only once, though it occurs in each string. The GST and GSA of strings apple and maple are shown in Figure 1.2.
这里有一篇关于构造 GSA 的算法的文章：
Generalized enhanced suffix array construction in external memory