У 1970 р. Д. Кнут, Дж. Морріс і В. Пратт запропонували алгоритм пошуку рядка в тексті, так званий КМП-алгоритм або КМП-пошук, фактично потребуючий тільки N порівнянь, навіть у найгіршому випадку.
Новий алгоритм ґрунтується на тому розумінні, що, починаючи щораз при неспівпаданні порівнювати образ-рядок із самого початку, можна знищити цінну інформацію. Після часткового збігу початкової частини образу-рядка з відповідними символами рядка-текста, фактично уже відома пройдена частина текста, і можна обчислити деякі відомості (на основі самого образу), за допомогою яких потім виконується біль швидке переміщення по тексту. На рис. 5.1 подано приклад зсуву образу-рядка, що шукається в тексті.
| Рядок (текст) | . . . | A | B | C | D | E | F | A | . . . |
| Образ | A | B | C | D | E | A | |||
| Зсув образа | A | B | . . . |
Рис. 5.1. Зсув образу ABCDEА
Після розбіжності символів "F" і "A" продовжити порівняння можна, змістивши образ на п’ять позицій. Очевидно, що зсув образу-рядка залежить від вмісту самого рядка. Так в прикладі рис. 5.2 після розбіжності символів ”В” та ”А” можна продовжити порівняння, змістивши образ тільки на один символ.
| Рядок (текст) | . . . | A | A | A | A | A | А | В | . . . |
| Образ | A | A | A | A | A | B | |||
| Зсув образу | A | A | A | A | A | B |
Рис. 5.2. Зсув образа AAAAAB
Оскільки зміщення образу, залежить тільки від самого образу, Д. Кнут, Дж. Морріс і В. Пратт запропонували до початку пошуку формувати масив d, у якому записувати значення зсувів для кожного символу образу-рядка, якщо розбіжність буде саме на цьому символі. У програмному прикладі 5.8 наведений приклад пошуку згідно з алгоритмом КМП.
{===== Програмний приклад 5.8 =====}
іnt KMPSearch (char s[N], char p[M])
{ іnt d[M], lp=strlen(p), ls=strlen(s);
//формування масиву d
іnt j=0; k=–1; d[0]=–1;
whіle (j<lp) //lp – фактична довжина образу
{ whіle((k>=0)&&(p[j]!=p[k]))k=d[k];
j++;k++;
іf (p[j]==p[k]) d[j]=d[k]; else d[j]=k;
}
//алгоритм пошуку
whіle((j<lp)&&(і<ls)) //ls – фактична довжина тексту
{ whіle((j>=0)&&(s[і]!=p[j])) j=d[j];
і++; j++;
}
іf (j==lp) return і–lp; else return –1;
}
Якщо (j == lp), отже образ у тексті знайдений, починаючи з номера і – lp.
В таблиці 5.1 наведено приклади значень образу-рядка і масиву d.
Таблиця 5.1
Образ і відповідний йому вмісту масиву
| Значення образу | Вміст масиву d |
| ABCDE AAAAA AAAAB AABCD | -1 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 1 0 0 |
Аналіз КМП-пошуку. Точний аналіз КМП-пошуку, як і сам його алгоритм, дуже складний. Автори доводять, що в середньому потрібно порядка М+N порівнянь символів, що значно краще, ніж М*N порівнянь у алгоритмі прямого пошуку.