我最近一直在更新我的算法知识，并一直在阅读后缀数组。我读过的每个文本都将它们定义为单个搜索字符串上的后缀数组，但有些文章提到它“微不足道”以概括为整个搜索字符串列表，但我不知道如何。
假设我正在尝试对单词列表进行简单的子字符串搜索，并希望返回与给定子字符串匹配的单词列表。天真的方法似乎是在我的列表中的单词之间插入词典结束字符“$”，将它们连接在一起，并从结果中生成一个后缀树。但这似乎会产生大量不相关的条目。如果我创建一个“banana$muffin”的源字符串，那么我最终会为“ana$muffin”生成我永远不会使用的后缀。
我将不胜感激有关如何正确执行此操作的任何提示，或者更好的是，指向一些处理这种情况的算法文本的指针。
在后缀数组中，您通常不使用字符串，只使用一个字符串。这将是带有一些 endtoken 的几个字符串的连接版本（每个字符串都有一个不同的）。对于后缀数组，您使用指针（或数组索引）来引用后缀（只需要第一个标记/字符的位置）。所以需要的空间是数组+每个后缀的指针。（这只是一个非常简单的实现，你应该做更多，以获得更高的性能）。
在这种情况下，您可以优化后缀的排序算法，因为您只需要对指针引用的那些后缀进行排序，直到 endtokens。endtoken 后面的所有东西都不需要在排序算法中使用。
在阅读了 Dan Gusfield 的《关于字符串、树和序列的算法》一书的大部分内容之后，答案似乎很清楚。
如果您从多字符串后缀树开始，其中一种标准转换算法仍然有效。但是，您最终得到的不是一个整数数组，而是一个列表数组。每个列表包含一对或多对字符串标识符和该字符串中的起始偏移量。
生成的结构仍然有用，但不如普通后缀数组有效。
来自爱荷华州立大学，取自Prefix.pdf：
后缀树和后缀数组可以泛化为多个字符串。一组字符串的广义后缀树 S = {s1, s2, . . . , sk}，表示为 GST(S) 或简称 GST，是 S 中每个字符串的所有后缀的压缩 trie。我们假设唯一的终止字符 $ 附加到每个字符串的末尾。叶标签现在由一对整数 (i, j) 组成，其中 i 表示后缀来自字符串 si，j 表示后缀在 si 中的起始位置。类似地，GST 中的边缘标签是其中一个字符串的子字符串。边标签由整数三元组 (i, j, l) 表示，其中 i 表示字符串编号，j 和 l 表示 si 中子字符串的开始和结束位置。为了方便理解，我们将继续展示实际的边缘标签。请注意，两个字符串可能具有相同的后缀。这是通过允许树中的叶子具有多个标签来补偿的。如果一个叶子被多重标记，每个后缀应该来自不同的字符串。如果 N 是 S 中所有字符串的字符总数（包括每个字符串中的 $），则 GST 最多有 N 个叶子节点，占用 O(N) 空间。S 的广义后缀数组，表示为 GSA(S) 或简称为 GSA，是 S 中每个字符串的所有后缀按字典顺序排序的数组。每个后缀由整数对 (i, j) 表示，表示从位置 j 开始的后缀西。如果来自不同字符串的后缀相同，则它们在 GSA 中占据连续的位置。为方便起见，我们将后缀 $ 作为一个例外，只列出一次，尽管它出现在每个字符串中。
这里有一篇关于构造 GSA 的算法的文章：