知识卡片

普通读书笔记卡 · 3704.d.1.d

新边界必由旧边界延长

理解等级:高级

对模式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]而来;计算新边界只须在旧边界链中找能延长的候选。

这张卡片看不懂?

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