知识卡片

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

前缀函数记录最长真前后缀

理解等级:初级

π[q]是模式前q个字符的最长真后缀长度,要求这个后缀同时是模式前缀,且长度严格小于q。

它只描述模式自身的重叠结构,不依赖待搜索文本。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      , m –} such that π[q] = max{k : k < q and P[:k] ⊐ P[:q]}. That is, π[q] is the length of the longest prefix of P that is a proper suffix of P[:q]. Here is the complete prefix function π for the pattern ababaca: Figure 32.9 The prefix function π. (a) The pattern P = ababaca aligns with a text T so that the first q = 5 characters

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[40000,45000))。 - 结论依据:原文第32.3–32.4节对应引理、转移表或前缀函数推导;图式已核对。 - 原始内容:For a given pattern P [1: m ], the prefix function for P is the function π : {1, 2, …, m } → {0, 1, …, m –} such that π [ q ] = max{ k : k < q and P [: k ] ⊐ P [: q ]}. That is, π [ q ] is the length of the longest prefix of P that is a proper suffix of P [: q ]. Here is the complete prefix function π for the pattern ababaca : Figure 32.9 The prefix function π . (a) The pattern P = ababaca aligns with a text T so that the first q = 5 characters