知识卡片
新边界必由旧边界延长
对模式P,π[q]是P[:q]的最长真边界长度,π[q−1]是从π[q−1]反复回退得到的全部真边界长度(含0)。若π[q]>0,则π[q]−1必在π[q−1]中:把P[:q]两端长度π[q]的相同片段同时删去末字符,就得到P[:q−1]的一个真边界。
因此,P[:q]的每个非空边界都由P[:q−1]的某个旧边界再匹配字符P[q]而来;计算新边界只须在旧边界链中找能延长的候选。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
, m, if π[q] > 0, then π[q] – 1 ∈ π*[q – 1]. Proof Let r = π[q] > 0, so that r < q and P[:r] ⊐ P[:q], and thus, r – 1 < q – 1 and P[:r – 1] ⊐ P[:q – 1] (by dropping the last character from P[:r] and P[:q], which we can do because r > 0). By Lemma 32.5, therefore, r – 1 ∈ π*[q –
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[45000,50000))。
- 结论依据:原文第32.4节的边界迭代引理、前缀函数证明或KMP状态转移推导。
- 原始内容:Lemma 32.6 Let P be a pattern of length m , and let π be the prefix function for P . For q = 1, 2, …, m , if π [ q ] > 0, then π [ q ] – 1 ∈ π *[ q – 1]. Proof Let r = π [ q ] > 0, so that r < q and P [: r ] ⊐ P [: q ], and thus, r – 1 < q – 1 and P [: r – 1] ⊐ P [: q – 1] (by dropping the last character from P [: r ] and P [: q ], which we can do because r > 0). By Lemma 32.5, therefore, r – 1 ∈ π *[ q –