请解释：
假设我们有一个对应于一个 n 字符文本的后缀数组，并且我们想要在一个 m 字符模式的文本中查找所有出现。由于后缀是有序的，最简单的解决方案是使用 O(log n) 比较对模式的第一次和最后一次出现（如果有）进行二进制搜索。
在确定 pattern 的第一次和最后一次出现后，我需要知道如何获得所有出现的 pattern。
问问题
80 次
1 回答
1
您引用的文字在两个方面有点令人困惑，甚至可能具有误导性：
它说找到模式的第一次和最后一次出现就足够了，但它应该更准确地说：后缀数组中模式的第一次和最后一次出现。这与基础文本中的第一次和最后一次出现不同。
它说你需要 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 回答