知识卡片

普通读书笔记卡 · 3707.b

模式出现对应后缀数组连续区间

理解等级:中级

所有以模式P开头的后缀在字典序中连续,因此可先二分找到一个命中,再向两侧扩展得到全部出现位置。

直接比较每次至多读m字符,查找加列举k处的成本为O(m lg n+km)。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[60000,65000))。 - 结论依据:原文第32.5节后缀数组、LCP和倍增构造的定义、示例或正确性推导。 - 原始内容: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