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 and pattern length of :

• Naive - It takes nil preprocessing and matching time.
• Rabin-Karp Algorithm - It takes preprocessing and matching time.
• Finite Automata - It takes preprocessing and matching time.
  
• Knuth-Morris-Pratt - It takes preprocessing and matching time.