Strings

Question 1

Name of O(n) algo for simple pattern matching a string of length n

Answer 1

KMP (Knuth Morris Pratt)

Question 2

Rabin Karp time complexity

Answer 2

average and best-case running time of the Rabin-Karp algorithm is O(n+m), but its worst-case time is O(nm).