通过后缀数组的最长公共子串：哨兵的使用
Longest common substring via suffix array: uses of sentinel
我正在阅读一系列字符串中最长公共子串的（显然）众所周知的问题，并且一直在关注这两个讨论如何使用后缀数组解决问题的视频：（注意这个问题不需要你看):
第一步是我们首先将所有源字符串连接成一个大字符串，用 'unique' 标记分隔每个标记，其中每个标记的 ASCII 码小于可能出现的任何字符的 ASCII 码出现在任何字符串中。所以我们可以有单独的字符串
abca
bcad
daca
并将它们连接起来得到
abca#bcad$daca%
现在，可能的哨兵数量有限，如果我们有大量的字符串，就会出现问题。事实上，有人在第一个链接视频中指出了这一点，对此的回应是
Correct, the solution is to map your alphabet to the natural numbers
and shift up by the number of sentinels you need. This allows you to
always have sentinels between the values say [1,N] and your alphabet
above that. This trick makes the suffix array scaleable, but you need
to undo the shift the decode the true value stored in the suffix
array.
我不明白这个答案是什么意思。
我知道我可以 post 在视频中提出我的问题，但不能保证（及时）回复我，而且这里的观众要广泛得多，所以我在这里问人：有人可以解释一下这个答案的含义以及如何实现吗？
不知道如何解释它 better/different 比在引用的评论中。也许一个例子会有所帮助。请注意，我在这里 不是 使用真正的 ASCII 代码，因为我不想显示包含约 100 个源字符串的示例。因此，我们只假设 A=1、B=2、C=3 等
因此，您的源字符串 abca bcad daca 将转换为 [1,2,3,1],[2,3,1,4],[4,1,3,1]，但为了适应三个标记，您必须将所有这些值向上移动 3，即 1 到 3现在哨兵和 A=4，B=5 等；加入的"string"（实际上，它现在是一个整数列表）是[4,5,6,4, 1, 5,6,4,7, 2, 7,4,6,4, 3]。然后，您可以将它们翻译回字符 defda...，执行算法，然后翻译回去，撤消转换。
但是，我认为我们可以将负数用于标记，然后直接处理整数列表而不是将它们转换回字符（这对于负数）：[1,2,3,1, -1, 2,3,1,4, -2, 4,1,3,1, -3]（注意：我没有看过视频，不知道这个特定算法是如何工作的；负数可能是个问题，例如在如果这是使用某种 "shortest path" 算法。）
我正在阅读一系列字符串中最长公共子串的（显然）众所周知的问题，并且一直在关注这两个讨论如何使用后缀数组解决问题的视频：（注意这个问题不需要你看):
第一步是我们首先将所有源字符串连接成一个大字符串，用 'unique' 标记分隔每个标记，其中每个标记的 ASCII 码小于可能出现的任何字符的 ASCII 码出现在任何字符串中。所以我们可以有单独的字符串
abca
bcad
daca
并将它们连接起来得到
abca#bcad$daca%
现在，可能的哨兵数量有限，如果我们有大量的字符串，就会出现问题。事实上，有人在第一个链接视频中指出了这一点，对此的回应是
Correct, the solution is to map your alphabet to the natural numbers and shift up by the number of sentinels you need. This allows you to always have sentinels between the values say [1,N] and your alphabet above that. This trick makes the suffix array scaleable, but you need to undo the shift the decode the true value stored in the suffix array.
我不明白这个答案是什么意思。
我知道我可以 post 在视频中提出我的问题，但不能保证（及时）回复我，而且这里的观众要广泛得多，所以我在这里问人：有人可以解释一下这个答案的含义以及如何实现吗？
不知道如何解释它 better/different 比在引用的评论中。也许一个例子会有所帮助。请注意，我在这里 不是 使用真正的 ASCII 代码，因为我不想显示包含约 100 个源字符串的示例。因此，我们只假设 A=1、B=2、C=3 等
因此，您的源字符串 abca bcad daca 将转换为 [1,2,3,1],[2,3,1,4],[4,1,3,1]，但为了适应三个标记，您必须将所有这些值向上移动 3，即 1 到 3现在哨兵和 A=4，B=5 等；加入的"string"（实际上，它现在是一个整数列表）是[4,5,6,4, 1, 5,6,4,7, 2, 7,4,6,4, 3]。然后，您可以将它们翻译回字符 defda...，执行算法，然后翻译回去，撤消转换。
但是，我认为我们可以将负数用于标记，然后直接处理整数列表而不是将它们转换回字符（这对于负数）：[1,2,3,1, -1, 2,3,1,4, -2, 4,1,3,1, -3]（注意：我没有看过视频，不知道这个特定算法是如何工作的；负数可能是个问题，例如在如果这是使用某种 "shortest path" 算法。）