知识卡片
模式出现对应后缀数组连续区间
所有以模式P开头的后缀在字典序中连续,因此可先二分找到一个命中,再向两侧扩展得到全部出现位置。
直接比较每次至多读m字符,查找加列举k处的成本为O(m lg n+km)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
Given the suffix array for a text, you can search for a pattern via binary search on the suffix array. Each occurrence of a pattern in the text starts some suffix of the text, and because the suffix array is in lexicographically sorted order, all occurrences of a pattern will appear at the start of consecutive entries of the suffix array. For example, in Figure 32.11, the three occurrences of at in ratatat appear in entries 1 through 3 of the suffix array. If you find the length-m pattern in the length-n suffix array via binary search (taking O(m 1g n) time because each comparison takes O(m) time), then you can find all occurrences of the pattern in the text by searching backward and forward from that spot until you find a suffix that does not start with the pattern (or