知识卡片

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

前缀表沿边界链递减搜索

理解等级:中级

COMPUTE-PREFIX-FUNCTION从前一项π[q−1]出发,失配就令k=π[k],按递减顺序检查所有候选边界。

遇到首个可延长边界置π[q]=k+1;到0后仍不匹配则置0。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      The while loop of lines 5–6 searches through all values k ∈ π*[q – 1] in decreasing order to find the value of π[q]. The loop terminates either because k reaches 0 or P[k + 1] = P[q]. Because the “and” operator short-circuits, if the loop terminates because P[k + 1] = P[q], then k must have also been positive, and so k is the greatest value in Eq–1. In this case, lines 7–9 set π[q] to k + 1, according to Corollary 32.7. If, instead, the while loop terminates because k = 0, then there are two possibilities. If P[1] = P[q], then Eq–1 = {0}, and lines 7–9 set both k and π[q] to 1. If k

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[50000,55000))。 - 结论依据:原文第32.4节的边界迭代引理、前缀函数证明或KMP状态转移推导。 - 原始内容:The while loop of lines 5–6 searches through all values k ∈ π *[ q – 1] in decreasing order to find the value of π [ q ]. The loop terminates either because k reaches 0 or P [ k + 1] = P [ q ]. Because the “and” operator short-circuits, if the loop terminates because P [ k + 1] = P [ q ], then k must have also been positive, and so k is the greatest value in E q –1 . In this case, lines 7–9 set π [ q ] to k + 1, according to Corollary 32.7. If, instead, the while loop terminates because k = 0, then there are two possibilities. If P [1] = P [ q ], then E q –1 = {0}, and lines 7–9 set both k and π [ q ] to 1. If k