Figure 32.3 A graphical proof of Lemma 32.I. We suppose that x ]a andy 1z onnect matching regions(shown shaded) of the strings. (a)If k< b, thenx ly. (b)If]d> b then ]x()If k]=b thenx=y Naive String matching algorithm ■■ Naive-String-matcher(T, P 2.m∈ . length[P 3.Fors∈0ton-m 1. IfP[L,-,m==T[+1,.,stm 1. Print"Pattern occurs with shifts Rabin Karp algorithm Key points of Karp-Rabin Hash Value p of a string P with modulo q How to compute the value efficiently? p=hash(P, m, q(P(mEP+ P(m-121+ P( J2P+ Plm-1JIEp+.+ P[=lm-l)mod( Ls+i=Hash(T[+1,m], m, q) 计算方法:多项式求值方法 ts+i =d(ts-TIsIh)T[s+m+l] mod(g) ·算法描述: h=dm-l(mod q) 给定字符串T和要找的子字符串P d是进位,如果是26个字符,则可以是26, If Hash(P/m, q)=Hash(T(L,m,m,q)c 般来讲取d为 ·继续判断(nave方法) Spurious Hit 其中Ti,m]表示T从开始长度为m的子串 lsl9lo2|34|52|6173992山 ·mod13 89|3l084|50u7gl valid (b)2 7 Figure 32.3 A graphical proof of Lemma 32.1. We suppose that x ] a and y ] z. The three parts of the figure illustrate the three cases of the lemma. Vertical lines connect matching regions (shown shaded) of the strings. (a) If |x| ≤ |y|, then x ] y. (b)If |x| ≥ |y|, then y ] x. (c) If |x| = |y|, then x = y. 8 Naïve String matching algorithm • Naïve-String-matcher(T,P) 1. nÅlength[T] 2. mÅlength[P] 3. For s Å0 to n-m 1. If P[1,…,m]==T[s+1,…,s+m] 1. Print “Pattern occurs with shift” s 9 Rabin Karp algorithm • Hash Value p of a string P with modulo q: – p=hash(P,m,q)=(P[m]|Σ| 0+ P[m-1]|Σ| 1+ P[m-2]|Σ| 2+…+ P[m-i]|Σ| i +…+ P[1]|Σ| m-1) mod(q) – 计算方法：多项式求值方法， • 算法描述： – 给定字符串T和要找的子字符串P， – 从i=1到Length[T]-Length[P] • If Hash(P,m,q)!=Hash(T[i,m],m,q) continue • 继续判断（naïve方法） • 其中T[i,m]表示T从i开始长度为m的子串 10 Key Points of Karp-Rabin • How to compute the value efficiently? – ts+1 = Hash(T[s+1,m],m,q) – ts+1 =(d(ts-T[s+1]h)+T[s+m+1]) mod(q) – h=dm-1 (mod q) – d是进位，如果是26个字符，则可以是26， 一般来讲取d为|Σ| • Spurious Hit 11 2 9 0 2 3 1 4 1 5 2 6 7 7 3 5 3 9 9 2 1 12 2 9 0 2 3 1 4 1 5 2 6 7 7 3 5 3 9 9 2 1 8 9 3 11 0 1 8 4 5 10 11 7 9 11