如何修改后缀数组以搜索多个字符串？

Question

我最近一直在更新我的算法知识，并一直在阅读后缀数组。我读过的每篇文章都将它们定义为单个搜索字符串上的后缀数组，但有些文章提到了将其概括为整个搜索字符串列表的“微不足道”，但我不知道如何。

假设我正在尝试对单词列表执行简单的子字符串搜索，并希望返回与给定子字符串匹配的单词列表。天真的方法似乎是在我的列表中的单词之间插入字典结束字符“$”，将它们连接在一起，然后从结果中生成后缀树。但这似乎会产生大量不相关的条目。如果我创建一个 'banana$muffin' 的源字符串，那么我最终会为我永远不会使用的 'ana$muffin' 生成后缀。

我很感激有关如何正确执行此操作的任何提示，或者更好的是，指向一些处理这种情况的算法文本的指针。

Answer 1

在读完《字符串、树和序列的算法》一书的大部分内容之后一书的大部分内容之后，答案似乎很清楚。

如果您从多字符串后缀树开始，标准转换算法之一仍然有效。但是，您最终得到的不是一个整数数组，而是一个列表数组。每个列表包含一对或多对字符串标识符和该字符串中的起始偏移量。

生成的结构仍然有用，但不如普通后缀数组高效。