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)