string - 将后缀按后缀数组排序有何意义？

Question

我知道后缀数组本身的定义是它是一个由字符串的所有后缀组成的排序数组。但我想弄清楚这次分类行动的意义是什么？假设我们创建了一个包含字符串所有后缀的数组，并选择不排序，继续构造LCP数组，那么在这种情况下，当我们试图解决诸如最长回文子字符串、最长重复子字符串等常见问题时，会有什么松动？

Answer 1

要将所有后缀排序到后缀数组中，有两个主要原因。
首先，如果s和t是字符串，我们知道：
t是s的子串if且仅当它是s后缀的前缀时。
例如，如果s是“avoidance”，t是“ida”，那么t是s的一个子串，因为它是后缀“idance”的前缀。因此，需要快速查询s的子串的应用程序可以根据搜索s的后缀前缀的方式重新措辞。
鉴于此，如果您对搜索s后缀的前缀感兴趣，那么将这些后缀存储在允许快速搜索的数据结构中是有意义的。如果我们把后缀放在一个数组中，保持它们的排序，然后允许您查找各种前缀必须有效的位置。因此，如果后缀数组是按排序顺序存储的S的所有后缀的数组，则可以快速搜索后缀的前缀，从而搜索S的子字符串。
至于你关于LCP数组的第二个问题，如果后缀没有排序，你能计算它们吗？如果排序了，你会失去什么-您绝对可以为任何数组计算它们，即使是后缀的非排序数组，因此没有根本原因不能这样做。但是，排序后缀数组的LCP数组有一系列好的属性，而未排序后缀数组的LCP数组没有这些属性例如，后缀数组中的lcp数组可用于确定相应后缀树中内部节点的深度，或计算最长公共扩展名等。
排序后缀数组和LCP的一个非常重要的特性是，如果计算所有字符串的成对LCP信息，可以通过对LCP数组执行范围最小查询来计算任意字符串对上的LCP之所以这样做是因为如果后缀被排序，则保留相邻字符串之间的最大重叠量。这在数组未排序的情况下不起作用（我将在最后再次提到这一点）
为了明确地了解事情的分解位置，让我们考虑最长的重复子串问题。使用后缀数组的正常线性时间算法如下：
为字符串T构造后缀数组。
为广义后缀数组构造lcp数组。
遍历后缀数组并找到其LCP值最大的字符串。
重要的是要想一想这最后一步为什么有效。考虑任何重复两次的子字符串，称之为s。因为任何子字符串都是后缀的前缀，这意味着字符串sα和sβ必须是字符串t的后缀。如果按排序顺序存储后缀数组，则以前缀s开头的所有字符串都将连续出现在后缀数组中（您明白为什么吗？）。因此，如果s是最长的重复子字符串，则以s开头的第一个后缀具有长度为s的下一个字符串的lcp。
现在，考虑一下如果在不排序数组的情况下执行此操作会发生什么情况。在这种情况下，如果s是最长的重复子串，那么字符串sα和sβ仍然是字符串t的后缀。但是，它们在后缀数组中不一定是连续的，因此不一定有线性时间算法来查找它们。例如，考虑字符串

abracadabra

未排序的后缀数组是

abracadabra$
bracadabra$
racadabra$
acadabra$
cadabra$
adabra$
dabra$
abra$
bra$
ra$
a$
$

在用LCP信息注释之后，我们得到

0 abracadabra$
0 bracadabra$
0 racadabra$
0 acadabra$
0 cadabra$
0 adabra$
0 dabra$
0 abra$
0 bra$
0 ra$
0 a$
  $

所以你可以看到这个算法找不到“abra”，因为它们不是连续的。你仍然可以通过尝试所有的对来理解它是“abra”，但是对于大型弦来说这是不有效的。
我之前提到过，关于排序后缀数组中相邻字符串对的LCP信息可用于计算排序后缀数组中任意字符串对的LCP信息如果字符串未排序，则情况并非如此；在上面，您可以看到字符串都具有相邻的成对LCP 0，即使某些字符串确实具有非零的公共前缀。
希望这有帮助！