2

我知道后缀数组本身的定义是它是一个字符串所有后缀的排序数组。但我想了解这里排序操作的意义是什么？假设我们创建了一个包含字符串所有后缀的数组并选择不对其进行排序并继续构建 LCP 数组，当我们尝试解决最长回文子字符串等常见问题时，我们在这种情况下会松动什么，最长重复子字符串？

4

1 回答 1

7

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

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

T 是 S 的子串当且仅当它是 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 开头的第一个后缀有一个 LCP，其下一个长度为 |S|。

现在，考虑一下如果你在不对数组进行排序的情况下这样做会发生什么。在这种情况下，如果 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 信息。如果字符串未排序，则不是这样；在上面，您可以看到字符串都具有 0 的相邻成对 LCP，即使某些字符串确实具有非零公共前缀。

希望这可以帮助！

于 2014-06-14T17:22:19.450 回答