text T a b a b a a b a b a 5=3 pattern P b a a Worst Case Algorithm Preprocessing time Matching time Naive 0 O((n-m+1)m) Rabin-Karp ⊙(m) O(n-m+1)m)） Finite automaton O(m∑) ⊙(n) Knuth-Morris-Pratt ⊙(m) Θ(n) n:the length of text T m:the length of pattern the alphabet set,consisiting ofall possible characters𝑛:𝑡ℎ𝑒 𝑙𝑒𝑛𝑔𝑡ℎ 𝑜𝑓 𝑡𝑒𝑥𝑡 𝑇 𝑚:𝑡ℎ𝑒 𝑙𝑒𝑛𝑔𝑡ℎ 𝑜𝑓 𝑝𝑎𝑡𝑡𝑒𝑟𝑛 𝛴:the alphabet set , consisiting of all possible characters Worst Case