请解释:
Suppose we have a suffix array corresponding to an n-character text and we want to find all occurrences in the text of an m-character pattern. Since the suffixes are ordered, the easiest solution is to do binary search for the first and last occurrences of the pattern (if any) using O(log n) comparisons.
我需要知道如何在确定模式的第一次和最后一次出现后获取模式的所有出现。
最佳答案
您引用的文字在两个方面有些困惑，甚至可能具有误导性:
它说找到模式的第一次和最后一次出现就足够了，但更准确地说，它应该说:在后缀数组中第一次和最后一次出现的模式。这与基础文本中的第一次和最后一次出现不同。
它说您需要 O(log n) 次比较。只有当“比较”指的是最多 m 个字符的字符串比较时，这才是正确的。由于比较最多 m 个字符需要 O(m) 时间，因此计算步骤数(例如在标准 RAM 模型中)为 O(m*log n)。如果构建和使用辅助数据结构，例如LCP(longest-common-prefix)数组，则可以对其进行改进。
现在，回答您的问题:考虑到上面的 (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 标记了模式的出现。
(请注意，实际上不使用后缀的完整字符串列表——仅使用整数位置列表。)
关于string - 无法理解http ://pine. cs.yale.edu/pinewiki/SuffixArrays中提到的概念，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11931345/