KMP liczy funkcję prefiksową (LPS), dzięki czemu przy niedopasowaniu przesuwa wzorzec bez ponownego sprawdzania znaków. To daje O(n+m) zamiast O(n·m).