知识卡片

普通读书笔记卡 · 3704.e

候选位移计数必须包含端点

理解等级:初级

长度n文本中搜索长度m模式,合法起点从0到n−m,共n−m+1个。

复杂度写成Θ(n−m+1)而非Θ(n−m),因为m=n时仍须检查唯一一个起点,成本为常数而非0。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      The “+1” is significant in an asymptotic sense because when m = n, computing the lone ts value takes Θ(1) time, not Θ(0) time. 3 Informally, lexicographic order is “alphabetical order” in the underlying character set. A more precise definition of lexicographic order appears in Problem 12-2 on page 327. 4 Why keep saying “length at most”? Because

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[100000,100814))。 - 结论依据:原文章末问题32-2给出的构造步骤、问题32-3给出的BWT定义及逆变换说明,或章末脚注。 - 原始内容:The “+1” is significant in an asymptotic sense because when m = n , computing the lone t s value takes Θ(1) time, not Θ(0) time. 3 Informally, lexicographic order is “alphabetical order” in the underlying character set. A more precise definition of lexicographic order appears in Problem 12-2 on page 327. 4 Why keep saying “length at most”? Because