后缀在后缀数组中排序的重要性是什么？

Question

我知道后缀数组本身的定义是它是一个字符串所有后缀的排序数组.但我试图了解这种排序操作的重要性在这里？假设我们创建了一个包含字符串所有后缀的数组,并选择不对其进行排序并继续构建LCP数组,当我们尝试解决诸如Longest Palindromic子字符串之类的常见问题时,我们在这种情况下会松动什么呢？最长的重复子串？

Answer 1

您希望将所有后缀排序在后缀数组中有两个主要原因.

首先,如果S和T是字符串,我们知道以下内容:

T是S的子串,当且仅当它是S的后缀的前缀时.

例如,如果S是"回避"而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,即使某些字符串肯定有非零公共前缀.

希望这可以帮助!