text T a b a b a a b a b a =3 pattern P b a a Algorithm Preprocessing time Matching time Naive 0 O(n-m+1)m) Rabin-Karp ⊙(m) O(n-m+1)m) Finite automaton O(1m∑) Θ(n) Knuth-Morris-Pratt Θ(1m) Θ(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