■ ■■口 Figure 32.8 An illustration for the proof of Lemma 32.2. The figure shows thats o(x)+ l, where r= o(xa) Figure 32.9 An illustration for the proof of Lemma 32.3 The figure shows thatr=o(Pa), where q=o(x) and r=o(xa) COMPUTE-TRANSITION-FUNCTION(P, 2) Knuth-Morris-Pratt Algorithm 7 mlength[PI 2forq←0tom ·中心思想:克服nave算法和有限自动机 3 do for each character a∈∑ 算法的重复工作! do k- min(m+1, 9+2) ·主要步骤:计算辅助函数π{1,2,,m它只 repeat k←k 与 Pattern相关,用来说明 Pattern的重复情 until Pk]P4【是后缀! 7 6q,a)←k 8 return 5 在某S处开始有5个字符匹配,第六个不匹配 这时找一个短一些的匹配串:即从第S+2处开 始的长度为3的地方匹配见下页 balc babr bac bababaa babr H blal lacal aa bl a ca5 25 Figure 32.8 An illustration for the proof of Lemma 32.2. The figure shows that r ≤ σ(x) + 1, where r = σ(xa). pr−1 pr 26 Figure 32.9 An illustration for the proof of Lemma 32.3. The figure shows that r = σ(Pqa), where q = σ(x) and r = σ(xa). pq pr 27 COMPUTE-TRANSITION-FUNCTION(P, ∑) 1 m←length[P] 2 for q ← 0 to m 3 do for each character a ∈ ∑ 4 do k ← min(m + 1, q + 2) 5 repeat k ← k － 1 6 until Pk ] Pqa【是后缀！】 7 δ(q, a) ← k 8 return δ 28 Knuth-Morris-Pratt Algorithm • 中心思想：克服naïve 算法和有限自动机 算法的重复工作！ • 主要步骤：计算辅助函数π[1,2,…,m]它只 与Pattern相关，用来说明Pattern的重复情 况。 29 a a b a a b c b a b a b a a b c b a b b c a 在某S处开始有5个字符匹配，第六个不匹配， 这时找一个短一些的匹配串：即从第S＋2处开 始的长度为3的地方匹配,见下页 30 a a b a a b c b a b a b a a b c b a b b c a