Алгоритм Кнута-Морріса-Пратта знаходить усі входження патерну в тексті за лінійний час O(n+m), наперед обчислюючи функцію відмови, тож курсор тексту ніколи не рухається назад.

Функція відмови (префіксна функція) для кожної позиції патерну зберігає довжину найдовшого власного префікса, що є також суфіксом. Вона підказує алгоритму, наскільки зсунути патерн після розбіжності.

За розбіжності функція відмови повідомляє КМП, яка частина патерну вже збіглася як префікс, тож алгоритм зсуває патерн замість того, щоб відмотувати текст. Кожен символ тексту перевіряється не більше сталого числа разів.

Наївний пошук може повторно порівнювати символи після кожного зсуву, що дає O(n·m) у найгіршому випадку. КМП повторно використовує інформацію з попередніх порівнянь, досягаючи O(n+m).

Її будують, зіставляючи патерн із самим собою: вказівник стежить за поточною довжиною префікса, подовжуючи її на збігу та відкочуючись через попередні значення відмови на розбіжності, усе за O(m) часу.

КМП працює за O(n+m) часу, де n — довжина тексту, а m — довжина патерну, і використовує O(m) додаткової пам'яті для таблиці відмови.

Так. Після повного збігу він використовує значення відмови останньої позиції патерну, щоб продовжити, тож перекривні входження, як-от AA в AAAA, усі звітуються.

Текстові редактори, пошук на кшталт grep, виявлення вторгнень, біоінформатика та інспекція мережевих пакетів використовують КМП або споріднені лінійні алгоритми зіставлення.

Бойєр-Мур сканує патерн справа наліво й може пропускати великі ділянки, часто швидший на практиці, тоді як КМП гарантує строгу лінійну межу й ніколи не рухає курсор тексту назад.

Порожній патерн за домовленістю збігається на кожній позиції. Ця симуляція очікує непорожній патерн, не довший за текст, для змістовного пошуку.