algorithm - 通过后缀数组 : uses of sentinel 的最长公共(public)子串

Question

我正在阅读一系列字符串中最长公共(public)子串的(显然)众所周知的问题，并且一直在关注这两个讨论如何使用后缀数组解决问题的视频:(请注意，这个问题没有'要求你观看它们):

https://youtu.be/Ic80xQFWevc

https://youtu.be/DTLjHSToxmo

第一步是我们首先将所有源字符串连接成一个大字符串，用“唯一”标记分隔每个标记，其中每个标记的 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.

我不明白答案是什么意思。

我知道我可以在视频上发布我的问题，但不能保证(及时)回复我，而且这里的观众要广泛得多，所以我在这里问人们:有人能解释一下吗这个答案意味着什么以及如何实现它？

Answer 1

不确定如何比引用的评论更好/不同地解释它。也许一个例子会有所帮助。请注意，我不在这里使用真正的 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 等；加入的“字符串”(实际上，它现在是一个整数列表)是 [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](注意:我有 没有看过视频，也不知道这个特定算法是如何工作的；负数可能是个问题，例如，如果这是使用某种“最短路径”算法。)