text T a b a b a a b a b a c S=3 pattern P a 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(mΣ) ⊙(n) Knuth-Morris-Pratt ⊙(m) ©(n)