KMP

Algoritmul care poartă numele lui Knuth, Morris și Pratt se bazează pe realizarea unei precalculări pe șirul de căutat și folosirea acesteia în etapa a doua, cea de căutare.

Timpul de procesare este liniar (de ordinul: lungimea șirului de căutat + lungimea textului).