知识卡片
前缀函数迭代列出全部边界
对模式P,π[q]是P[:q]的最长真边界长度;“边界”指同时是前缀和后缀、但短于整个字符串的部分。从π[q]开始反复取π,直到0,得到的集合π*[q]恰好列出P[:q]的全部真边界长度。
这是因为任一更短边界也是最长边界P[:π[q]]的边界;反过来,最长边界的每个边界也会落在P[:q]的首尾。每次回退因而保留了所有仍可能与已读文本对齐的候选,KMP不必逐一试探每个较短长度。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
, m, we have π*[q] = {k : k < q and P[:k] ⊐ P[:q]}. Proof We first prove that π*[q] ⊆ {k : k < q and P[:k] ⊐ P[:q]} or, equivalently, If i ∈ π*[q], then i = π(u)[q] for some u > 0. We prove equation (32.7) by induction on u. For u = 1, we have i = π[q], and the claim follows since i
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[45000,50000))。
- 结论依据:原文第32.4节的边界迭代引理、前缀函数证明或KMP状态转移推导。
- 原始内容:Lemma 32.5 (Prefix-function iteration lemma) Let P be a pattern of length m with prefix function π . Then, for q = 1, 2, …, m , we have π *[ q ] = { k : k < q and P [: k ] ⊐ P [: q ]}. Proof We first prove that π *[ q ] ⊆ { k : k < q and P [: k ] ⊐ P [: q ]} or, equivalently, If i ∈ π *[ q ], then i = π ( u ) [ q ] for some u > 0. We prove equation (32.7) by induction on u . For u = 1, we have i = π [ q ], and the claim follows since i