Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 32

The authors define the problem of string matching and discuss following four algorithms with text length of $n$ and pattern length of $m$:

• Naive - It takes nil preprocessing and $O((n-m+1) \times m)$ matching time.
• Rabin-Karp Algorithm - It takes $\Theta(m)$ preprocessing and $O(n-m+1) \times m)$ matching time.
• Finite Automata - It takes $O(m \times |\sum|)$ preprocessing and $\Theta(n)$ matching time.
  
• Knuth-Morris-Pratt - It takes $\Theta(m)$ preprocessing and $\Theta(n)$ matching time.