Automaton for“ ababa 9ab④⑤⑥ 其它转移如何做? 自动机工作的一个例子 1 3 13 02040402 34567891011 b a b a b a c a b 51 68 (T)01234545672 71 算法描述: 后缀函数σ的属性: 【引定理32.2/3/4】 Finite-Automaton- Matcher(T, 8, m) If q=o(x)then o(xa=o(Poa) 6q,T) 如果ψ是模式P决定的自动机的最终状态 2. If q==m then print"pattern occurs at"i-m 函数,则(T=0(T4 19 Automaton for “ababaca” 0 1 2 3 4 5 6 7 其它转移如何做？ 转移函数？ 20 0 1 2 3 4 5 6 7 21 1 0 0 1 2 0 3 0 0 1 4 0 5 0 0 1 4 6 7 0 0 1 2 0 22 自动机工作的一个例子 i — 1 2 3 4 5 6 7 8 9 10 11 T[i] — a b a b a b a c a b a stateφ(Ti ) 0 1 2 3 4 5 4 5 6 7 2 3 23 算法描述： • Finite-Automaton-Matcher(T,δ,m) 1. n=length[T] 2. q=0 3. For i = 1 to n 1. q=δ(q,T[i]) 2. If q==m then print “pattern occurs at” i-m 24 后缀函数σ的属性： 【引/定理32.2/3/4】 • σ(xa)≤ σ(x)+1 • If q= σ(x) then σ(xa)=σ(Pqa) • 如果φ是模式P决定的自动机的最终状态 函数，则φ(Ti )=σ(Ti )