What is the preprocessing time complexity of the Knuth-Morris-Pratt (KMP) string matching algorithm for a pattern of length m?

Theta(m)

KMP precomputes a 'failure function' or prefix function that allows the search to skip characters that have already been matched. This preprocessing depends only on the length of the pattern, not the text.