知识卡片

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

前缀函数给出下一候选位移

理解等级:中级

已匹配q字符后失配,令k=π[q],下一可能有效的位移是s′=s+(q−k)。此前k字符必然与已读文本对齐,无需重比;选最长可复用前缀对应最小安全位移,避免漏匹配。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Given that q characters have matched successfully at shift s, the next potentially valid shift is at s′ = s + (q – π[q]) as shown in part (b). The procedure KMP-MATCHER on the following page gives the Knuth-Morris-Pratt matching algorithm. The procedure follows from FINITE-AUTOMATON-MATCHER for the most part. To compute π, KMP-MATCHER calls the auxiliary procedure COMPUTE-PREFIX-FUNCTION. These two

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[40000,45000))。 - 结论依据:原文第32.3–32.4节对应引理、转移表或前缀函数推导;图式已核对。 - 原始内容:Given that q characters have matched successfully at shift s , the next potentially valid shift is at s ′ = s + ( q – π [ q ]) as shown in part (b). The procedure KMP-M ATCHER on the following page gives the Knuth-Morris-Pratt matching algorithm. The procedure follows from F INITE -A UTOMATON -M ATCHER for the most part. To compute π , KMP-M ATCHER calls the auxiliary procedure C OMPUTE -P REFIX -F UNCTION . These two