Алгоритм Кнута-Морриса-Пратта (КМП) получает на  вход слово   X=x[1]x[2]... x[n]  и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]... l[n], где   l[i]=длина слова l(x[1]...х[i])  (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x[1]...x[i], одновременно являющегося его концом.