知识卡片
前缀表回退总量被增长量约束
构造π时,匹配长度k每轮最多增长1,总增长不超过m−1;失配循环每次都使k下降且k不为负,所以总下降次数也不超过m−1。
虽有嵌套while,整表仍只需Θ(m)时间。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
The running time of COMPUTE-PREFIX-FUNCTION is Θ(m), which we show by using the aggregate method of amortized analysis (see Section 16.1). The only tricky part is showing that the while loop of lines 5–6 executes O(m) times altogether. Starting with some observations about k, we’ll show that it makes at most m–1 iterations. First, line 3 starts k at 0, and the only way that k increases is by the increment operation in line 8, which executes at most once per iteration of the for loop of lines 4–9. Thus, the total increase in k is at most m
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[40000,45000))。
- 结论依据:原文第32.3–32.4节对应引理、转移表或前缀函数推导;图式已核对。
- 原始内容:The running time of C OMPUTE -P REFIX -F UNCTION is Θ( m ), which we show by using the aggregate method of amortized analysis (see Section 16.1 ). The only tricky part is showing that the while loop of lines 5–6 executes O ( m ) times altogether. Starting with some observations about k , we’ll show that it makes at most m –1 iterations. First, line 3 starts k at 0, and the only way that k increases is by the increment operation in line 8, which executes at most once per iteration of the for loop of lines 4–9. Thus, the total increase in k is at most m