知识卡片
可延长边界决定前缀函数
设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]时从首字符重新开始的匹配。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
If Eq–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.
参考来源
- 位置:《算法导论(第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.