Algorithms‎ > ‎

String Matching

The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T.

Text T                   a b c a b a a b c a b a c

pattern P  s = 3             a b a a

valid shift s = 3

Algorithm                        Processing time        Matching time

Native                                0                        O((n - m + 1)m)
Rabin-Karp                        O(m)                     O((n - m + 1)m)
Finite automation              O(m|E|)                          O(n)
Knuth-Morris-Pratt             O(m)                              O(n)