知识卡片

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

可延长边界决定前缀函数

理解等级:高级

设P是长度m的模式,π[q]是P[:q]的最长真边界长度,π[q−1]列出P[:q−1]的全部真边界长度并包含0。求q=2..m的π[q]时,从π[q−1]筛出满足P[k+1]=P[q]的可延长边界k,得到集合E(q−1)。

  • 若E(q−1)为空,则π[q]=0;
  • 否则π[q]=1+max E(q−1)。

候选k延长后形成长度k+1的新边界,取最大者就得到最长边界。还须检查空边界k=0,才能识别P[q]=P[1]时从首字符重新开始的匹配。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[50000,55000))。 - 结论依据:第32.4节推论32.7限定 q=2..m;公式图 Art_P1311 的分段式为 E_{q−1}=∅ 时 π[q]=0,否则 π[q]=1+max E_{q−1}。Art_P1312–P1313 分别证明下界和上界;原文明确 E 的候选含 k=0。 - 原始内容:If E q –1 is empty, there is no k ∈ π *[ q – 1] (including k = 0) such that extending P [: k ] to P [: k + 1] produces a proper suffix of P [: q ]. Therefore, π [ q ]= 0.