知识卡片
候选位移计数必须包含端点
长度n文本中搜索长度m模式,合法起点从0到n−m,共n−m+1个。
复杂度写成Θ(n−m+1)而非Θ(n−m),因为m=n时仍须检查唯一一个起点,成本为常数而非0。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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