roa*_*007 4 algorithm suffix-tree suffix-array
我正在尝试完成 Coursera 上的字符串算法课程，并且坚持使用此视频中描述的构建 LCP 数组的方法：
https://www.coursera.org/learn/algorithms-on-strings/lecture/HyUlH/computing-the-lcp-array
我很难理解这个视频中提出的理论。根据我自己的研究（谷歌搜索），我认为他们所描述的是 Kasai 的算法。但就像视频一样，所有的解释都使用非常抽象的解释或大量的代码样本。在不了解理论的情况下，我发现代码示例难以理解。我只是想用真实世界的例子来寻找解释。
即： S=ababaa$ 使用 Kasai 算法产生最终 LCP 数组的步骤是什么。
我正在使用 Kasai 等人的算法。正如本文图 3 中定义的那样。请注意，该论文有一个错字，其中j突然出现的应该是k. 我将索引更改为从0ton-1而不是1to n，以便与常见的编程语言更加一致。我也改名为输入字符串S，并Height到LCP：
Algorithm GetLCP:
input: A text S and its suffix array Pos
1 for i:=0 to n-1 do
2 Rank[Pos[i]] := i
3 od
4 h:=0
5 for i:=0 to n-1 do
6 if Rank[i] > 0 then
7 k := Pos[Rank[i]-1]
8 while S[i+h] = S[k+h] do
9 h := h+1
10 od
11 LCP[Rank[i]] := h
12 if h>0 then h := h-1 fi
13 fi
14 od
该算法将字符串S及其后缀数组（必须由其他算法计算）作为输入。因此，让我们首先计算示例 string 的后缀数组S=ababaa$。取所有可能的后缀S并将它们按字典序排序给我们（注意空后缀$已被省略，因为它不是很有趣，因为它总是在后缀数组中的第一个并且与下一个后缀没有共同的前缀；在下面，当我谈论所有就够了时，我的意思是除了空后缀之外的所有）：
| Suffix | Starts at |
-----------------------
| a$ | 5 |
| aa$ | 4 |
| abaa$ | 2 |
| ababaa$ | 0 |
| baa$ | 3 |
| babaa$ | 1 |
-----------------------
在论文的伪代码中，后缀数组被称为Pos，保存每个后缀的起始位置。所以在我们的例子中，我们会有Pos = [5,4,2,0,3,1]. 如果我们查询例如Pos[0]我们会得到5，它告诉我们字典序最小的后缀a$从位置 5 开始S。
该Rank数组旨在作为 的反向查找Pos。后缀的排名是它在后缀数组中的位置，即它在后缀的字典顺序中的排名。因此，如果Rank[i] = j，则从 的i第 位置开始的后缀S位于j后缀数组中的位置，所以Pos[j] = i。从伪代码中可以看出，Rank可以通过设置 来计算数组Rank[Pos[i]] = i。
| Starts At | Rank |
-----------------------
| 0 | 3 |
| 1 | 5 |
| 2 | 2 |
| 3 | 4 |
| 4 | 1 |
| 5 | 0 |
-----------------------
所以我们有Rank = [3, 5, 2, 4, 1, 0]. 我们可以看到，例如babaa$，从位置1in开始的后缀S有Rank[1] = 5，因此可以在后缀数组中的位置 5 处找到后缀。在倒车时，Pos[5] = 1由于在后缀数组中的位置5上的后缀开始于位置1中S。
伪代码中的循环现在迭代 中的位置S：
i=0: 我们正在查看从位置0in开始的后缀S，即ababaa$。我们有Rank[0] = 3，也就是> 0，所以我们知道后缀在后缀数组中有一个前面的后缀。
我们要确定这个前一个后缀的起始位置。前面的后缀位于Rank[0]-1=2后缀数组中的位置。我们有Pos[2] = 2。因此，后缀ababaa$数组中前面的后缀是abaa$，从位置2in开始S。我们设置k为这个起始位置，所以k=2.
我们确定从i=0和开始的前缀的最长公共前缀k=2。我们目前没有关于它们有多少共同点 ( h=0) 的信息，因此我们从起始位置比较两者就足够了：
ababaa$
abaa$
我们看到最长公共前缀的长度是3。所以我们设置h=0+3和LCP[Rank[0]] = LCP[3] = 3。然后我们减h一，所以h=3-1=2。
i=1: 我们正在查看从位置1in开始的后缀S，即babaa$。我们有Rank[1] = 5，也就是> 0，所以我们知道后缀在后缀数组中有一个前面的后缀。
我们要确定这个前一个后缀的起始位置。前面的后缀位于Rank[1]-1=4后缀数组中的位置。我们有Pos[4] = 3。因此，后缀babaa$数组中前面的后缀是baa$，从位置3in开始S。我们设置k为这个起始位置，所以k=3.
我们确定从 i=1 和 k=3 开始的后缀的最长公共前缀。从前面的迭代中，我们有h=2，所以我们已经知道 suffices 的前两个字符匹配，所以我们可以从第三个字符开始比较：
ba|baa$
ba|a$
我们立即有一个不匹配，所以没有h=2做任何改变。我们设置LCP[Rank[1]] = LCP[5] = 2。我们减h一，所以h现在是h=2-1=1。
i=2: 我们正在查看从位置2in开始的后缀S，即abaa$。我们有Rank[2] = 2，也就是> 0，所以我们知道后缀在后缀数组中有一个前面的后缀。
我们要确定这个前一个后缀的起始位置。前面的后缀位于Rank[2]-1=1后缀数组中的位置。我们有Pos[1] = 4。因此，后缀abaa$数组中前面的后缀是aa$，从位置4in开始S。我们设置k为这个起始位置，所以k=4.
我们确定从 i=2 和 k=4 开始的后缀的最长公共前缀。从之前的迭代中，我们有h=1，所以我们已经知道第一个字符就足够了，所以我们可以从第二个字符开始比较：
a|baa$
a|a$
我们立即得到一个不匹配，所以没有h=1做任何改变。我们设置LCP[Rank[2]] = LCP[2] = 1。我们减h一，所以h现在是h=1-1=0。
i=3: 我们正在查看从位置3in开始的后缀S，即baa$。我们有Rank[3] = 4，也就是> 0，所以我们知道后缀在后缀数组中有一个前面的后缀。
我们要确定这个前一个后缀的起始位置。前面的后缀位于Rank[3]-1=3后缀数组中的位置。我们有Pos[3] = 0。因此，后缀baa$数组中前面的后缀是ababaa$，从位置0in开始S。我们设置k为这个起始位置，所以k=0.
我们确定从 i=3 和 k=0 开始的后缀的最长公共前缀。从之前的迭代开始，我们有h=0，所以我们目前没有关于两个足够多有多少共同点的信息，所以我们必须从第一个字符开始比较：
baa$
ababaa$
我们立即得到一个不匹配，所以没有h=0做任何改变。我们设置LCP[Rank[3]] = LCP[4] = 0。由于h=0，我们不会h进一步递减。
i=4: 我们正在查看从位置4in开始的后缀S，即aa$。我们有Rank[4] = 1，也就是> 0，所以我们知道后缀在后缀数组中有一个前面的后缀。
我们要确定这个前一个后缀的起始位置。前面的后缀位于Rank[4]-1=0后缀数组中的位置。我们有Pos[0] = 5。因此，后缀aa$数组中前面的后缀是a$，从位置5in开始S。我们设置k为这个起始位置，所以k=5.
我们确定从i=4和开始的后缀的最长公共前缀k=5。从之前的迭代中，我们有h=0，所以我们目前没有关于两个足够多有多少共同点的信息，所以我们必须从第一个字符开始比较：
aa$
a$
我们看到最长公共前缀的长度为 1，因此我们设置h=0+1。我们设置LCP[Rank[4]] = LCP[1] = 1。我们减h一，所以h=1-1=0。
i=5: 我们正在查看从位置5in开始的后缀S，即a$。我们有Rank[5] = 0，但不是> 0，所以我们知道后缀数组中没有前面的后缀。因此，我们跳过计算 LCP。
总之，我们获得了以下 LCP 条目：
| Suffix | LCP with prev |
---------------------------
| a$ | n/a |
| aa$ | 1 |
| abaa$ | 1 |
| ababaa$ | 3 |
| baa$ | 0 |
| babaa$ | 2 |
-----------------------
我们可以验证 LCP 中的每个条目都为我们提供了具有前一个后缀的最长公共前缀的长度。
应该清楚，如果h=0，算法是正确的，因为它只是从第一个字符开始比较当前后缀和它在后缀数组中的前任。所以我们只需要验证 when h>0，h比较中跳过的suffice的第一个字符已经匹配。
让我们看看示例中的前两次迭代。第一次迭代是查看后缀数组中ababaa$首先出现的后缀S及其前身abaa$。在第二次迭代中，我们查看了后缀数组中的后缀babaa$及其前身baa$。
i=0
ababaa$
abaa$
i=1
babaa$
baa$
因为i=0我们找到了匹配 ( h=3)的前三个字符。然后我们减h一，导致h=2。在第二次迭代中，我们发现第一个h=2字符匹配就够了。这是为什么？当我们向右移动一个位置时，babaa$通过删除 的第一个字符获得后缀ababaa$。我们看到，后缀数组中baa$的前驱babaa$，恰好是去掉后缀数组中abaa$的前驱的第一个字符得到的ababaa$。因此，如果ababaa$后缀数组中的 LCP及其前身的长度为3，那么如果我们考虑通过从每个字符中删除第一个字符获得的后缀，则这些后缀的 LCP 的长度为 是有道理的3-1=2。
所以对于这个例子，我们看到 LCP fori=1是i=0负一的 LCP 。所以下一个要问的问题是，这通常是真的吗？答案是否定的。一般来说，如果我们从一个迭代移动i到另一个迭代i+1，可能会发生这样的情况，第i+1th 后缀在后缀数组中的前辈i与第一个删除了第一个字符的后缀数组中的前辈不相等。
考虑i=2和i=3在示例中。在 中i=2，我们正在查看 suffix abaa$，它aa$在 suffix 数组中具有前身。在 中i=3，我们正在查看 suffix baa$，它作为ababaa$suffix 数组中的前身。
i=2
abaa$
aa$
i=3
baa$
ababaa$
的前身i=3（ababaa$）是从不等于前身i=2与第一字符删除（a$）。但是，我们可以观察到，在后缀数组中，i=3( ababaa$)的前驱被“夹在”在后缀 from i=3( baa$) 和前驱 from 之间i=2，并且去掉了第一个字符 ( a$)。即在后缀数组中，ababaa$出现在a$和之间baa$。这是因为在后缀数组中直接在i=2后缀abaa$前面aa$（即按aa$字典序小于abaa$）并且它们的 LCP 的长度为>0. 因此，由此得出除去每个第一字符的情况下，产生的两个就足够将仍然具有相同的字典式顺序，即a$按字典顺序小于baa$，因此a$来之前baa$的后缀数组英寸 因此，baa$后缀数组 ( ababaa$) 中的直接前驱必须出现在a$和之间baa$。这种“夹心”是 Kasai 算法的关键洞察力。
让我们看一个不同的例子来说明这一点。让S = aaababab. 后缀数组将是：
| Suffix | Starts at |
-------------------------
| aaababab$ | 0 |
| aababab$ | 1 |
| ab$ | 6 |
| abab$ | 4 |
| ababab$ | 2 |
| b$ | 7 |
| bab$ | 5 |
| babab$ | 3 |
-------------------------
在迭代中i=0什么也没有发生，因为后缀aaababab$在后缀数组中没有前任。在迭代中，i=1我们将查看 suffix aababab$，它aaababab$在 suffix 数组中具有前身。在迭代中，i=2我们将查看后缀ababab$（从 中的后缀中删除第一个字符i=1）。它在后缀数组中的前身是abab$.
i=1
aababab$
aaababab$
i=2
ababab$
abab$
我们可以看到i=2( abab$) 中的前驱i=1与删除了第一个字符 ( aababab$) 中的前驱不同。但是，在后缀数组中，aababab$是“夹在”来自i=2( ababab$) 及其实际前身 ( abab$)的后缀。在i=1我们确定 的 LCPaababab$及其前身aaababab$是h=2。在迭代结束时，我们减h一，所以h=2-1=1。在 中i=2，我们然后看到我们确实可以跳过第一个字符的比较。这是因为我们知道后缀 from i=2( ababab$) 和i=1去掉第一个字符的前导 from ( aababab$) 将至少在第一个匹配2-1=1字符，因为两者都是从 suffices 中获得的i=1（在前两个字符中匹配），删除了第一个字符。此外，因为后缀数组是按字典顺序排序的，我们知道夹在这两者之间的所有后缀也将具有相同的第一个2-1=1字符。因此，当我们计算 中的 LCP 时i=2，跳过第一个2-1=1字符是有效的。
这通常是正确的：当我们从迭代i到迭代时i+1，对于迭代i+1中的后缀，后缀数组中的直接前驱夹在迭代后缀和迭代i+1前驱之间，i其中第一个字符被删除。迭代的后缀i+1和i删除第一个字符的迭代的前驱之间的 LCP等于迭代的 LCPi减一。因为后缀 in 的前驱i+1夹在迭代的后缀和迭代i+1的前驱之间，并且i去掉了第一个字符，所以 LCP fromi+1至少是 fromi，减一。因此，在算法中，h在计算 LCP 时跳过第一个字符是有效的。这是上面链接的论文中的定理 1。