Rabin-Karp-Matcher(T, P,d, q) 1.n= length们 ld 2. m=length[Pl digit shift 3. h=dm-l(mod q) 4.p=0 6. For i=l to m 8(mod13) 1, p=(dptPo)(mod q) 2. to=(dto+T)(mod q) 7. For s=0 to n-m PI1,…,mF=s-…m+ sh print" pattem occurs I. td(t-Ts+Ih+T[s+m+l] mod(q) String matching with finite 有限自动机示例:同 有限自动机M:5uple(Q40A,x,6) Q is a finite set of states a go in Q is the start state A contains inQ is a distinguished set of accepting states 2 is a finite input alphabet 6 is a function from q×∑ into Q called the abana accepted transition function of m abbbaaa accepte abba rejected Final-state function String matching automata 中Σ*→Q M=(Qq0A,∑。) where P(E=go ∑= the alphabet in P ￠wa=6(φw,a) for w in 2*,ainΣ m: Integer s means the current state has exactly s characters match the patter m=length(PI A={m} 6:5(q1a=G(Pa)2o(x=max{kPk2x,P表示 的前k个字符,称为后缀函数。【研究!】3 13 3 1 4 1 5 2 7 8 14152≡(31415－3·10000) · 10+2(mod 13) ≡(7－3 · 3) · 10+2(mod 13) ≡8(mod 13) 14 • Rabin-Karp-Matcher(T,P,d,q) 1. n=length[T] 2. m=length[P] 3. h=dm-1 (mod q) 4. p=0 5. T0=0 6. For i =1 to m 1. p=(dp+P[i]) (mod q) 2. t0=(dt0+T[i]) (mod q) 7. For s = 0 to n-m 1. If p=ts 1. If P[1,…,m]=T[s,…,m+s], print “pattern occurs at ” s 2. If s<n-m 1. ts+1=(d(ts-T[s+1]h)+T[s+m+1] mod(q) 15 String matching with finite automata • 有限自动机 M：5-tuple (Q,q0,A,Σ,δ) • Q is a finite set of states • q0 in Q is the start state • A contains in Q is a distinguished set of accepting states • Σ is a finite input alphabet • δ is a function from Q×Σ into Q called the transition function of M 16 有限自动机示例: 0 1 1 0 0 0 1 0 state a b input δ ? Σ ? A 1 q ? 0 Q ? abaaa accepted abbbaaa accepted abbaa rejected 17 Final-state function • φ: Σ∗ ÆQ • φ(ε)=q0 • φ(wa)=δ(φ(w),a) for w in Σ∗, a in Σ 18 String matching automata • Given pattern P, to construct an automaton: • M= (Q,q0,A,Σ,δ) where • Σ = the alphabet in P • Q = {0,1,2,…,m: integer s means the current state has exactly s characters match the pattern}, m=length[P] • q0=0 • A={m} • δ : δ(q,a)=σ(Pqa), σ(x)=max{k:Pk =x}, Pk表示P 的前k个字符，称为后缀函数。【研究！】