知识卡片

普通读书笔记卡 · 3706.b.3

后缀递推只需保留当前匹配前缀

理解等级:高级

设P是固定模式,σ(x)表示“既是x的后缀、又是P的前缀”的最长字符串长度,P[:q]表示P的前q个字符。若q=σ(x),对新字符a有

σ(xa)=σ(P[:q]a)。

原因是任何能在xa末尾继续成立的模式前缀,长度都不超过q+1;判断它时只需看x末尾已经匹配的P[:q]和新字符a。于是已经读过的长文本x无需保留全文,只须保存整数状态q,这正是有限自动机能在线跟踪匹配的关键。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Lemma 32.3 (Suffix-function recursion lemma) For any string x and character a, if q = σ(x), then σ(xa) = σ(P[:q]a). Proof The definition of σ gives that P[:q] ⊐ x. As Figure 32.8 shows, we also have P[:q]a ⊐ xa. Let r = σ(xa). Then P[:r] ⊐ xa and, by Lemma 32.2, r ≤ q + 1. Thus, we have |P[:r]| = r ≤ q + 1 = |P[:q]a|. Since P[:q]a ⊐ xa, P[:r] ⊐ xa, and |P[:r]| ≤ |P[:q]a|, Lemma

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[30000,35000))。 - 结论依据:原文第32.3–32.4节对应引理、转移表或前缀函数推导;图式已核对。 - 原始内容:Lemma 32.3 (Suffix-function recursion lemma) For any string x and character a , if q = σ ( x ), then σ ( xa ) = σ ( P [: q ] a ). Proof The definition of σ gives that P [: q ] ⊐ x . As Figure 32.8 shows, we also have P [: q ] a ⊐ xa . Let r = σ ( xa ). Then P [: r ] ⊐ xa and, by Lemma 32.2, r ≤ q + 1. Thus, we have | P [: r ]| = r ≤ q + 1 = | P [: q ] a |. Since P [: q ] a ⊐ xa , P [: r ] ⊐ xa , and | P [: r ]| ≤ | P [: q ] a |, Lemma