0

请解释：

假设我们有一个对应于一个 n 字符文本的后缀数组，并且我们想要在一个 m 字符模式的文本中查找所有出现。由于后缀是有序的，最简单的解决方案是使用 O(log n) 比较对模式的第一次和最后一次出现（如果有）进行二进制搜索。

在确定 pattern 的第一次和最后一次出现后，我需要知道如何获得所有出现的 pattern。

4

1 回答 1

1

您引用的文字在两个方面有点令人困惑，甚至可能具有误导性：

  1. 它说找到模式的第一次和最后一次出现就足够了，但它应该更准确地说：后缀数组中模式的第一次和最后一次出现。这与基础文本中的第一次和最后一次出现不同。

  2. 它说你需要 O(log n) 比较。仅当“比较”指的是最多 m 个字符的字符串比较时，这才是正确的。由于最多比较 m 个字符需要 O(m) 时间，因此计算步骤数（例如在标准 RAM 模型中）为 O(m*log n)。如果构建和使用辅助数据结构，例如 LCP（最长公共前缀）数组，则可以改进它。

现在，回答你的问题：考虑到上面的（1.），你很容易得到所有出现的模式，因为后缀数组是按字典顺序排序的。这意味着第一次出现是字典顺序最小的，最后一次出现是字典顺序最大的。因此，剩余的事件必须在第一个和最后一个之间。

例子。考虑字符串bcfabcabxbbcabcgdebcd。它的后缀数组（表示为后缀的起始位置，从0开始计数）是

[3, 12, 6, 9, 10, 4, 18, 0, 13, 7, 11, 5, 19, 1, 14, 20, 16, 17, 2, 15, 8]

对应于以下后缀列表：

3  : abcabxbbcabcgdebcd
12 : abcgdebcd
6  : abxbbcabcgdebcd
9  : bbcabcgdebcd
10 : bcabcgdebcd            <======= first occurrence of 'bc'
4  : bcabxbbcabcgdebcd
18 : bcd
0  : bcfabcabxbbcabcgdebcd
13 : bcgdebcd               <======= last occurrence of 'bc'
7  : bxbbcabcgdebcd
11 : cabcgdebcd
5  : cabxbbcabcgdebcd
19 : cd
1  : cfabcabxbbcabcgdebcd
14 : cgdebcd
20 : d
16 : debcd
17 : ebcd
2  : fabcabxbbcabcgdebcd
15 : gdebcd
8  : xbbcabcgdebcd

假设您要查找的模式是“bc”。我已经在后缀数组中标记了该模式的第一次和最后一次出现。由于字典排序，介于两者之间的所有条目也必须以“bc”开头，并且任何以“bc”开头的条目都必须介于两者之间。因此，所有以'bc' 开头的后缀，即'bc' 出现的所有位置，必须在第一次和最后一次出现之间。

表示为位置整数，我们确定的范围是

[10, 4, 18, 0, 13]

因此，位置 10、4、18、0 和 13 标记了该模式的出现。

（请注意，实际上不使用后缀的完整字符串列表 - 仅使用整数位置列表。）

于 2012-08-14T02:08:44.803 回答