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)