Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) работает следующим образом: 4

1. Даны образец (строка) S и строка T. 4 Требуется определить индекс, начиная с которого образец S содержится в строке T. 4 Если S не содержится в T — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). 4
2. Идея алгоритма состоит в том, чтобы не прикладывать подстроку к строке со сдвигом всего в один символ, а максимально увеличить это расстояние, сократив таким образом количество сравнений. 2
3. Первоначально необходимо найти все префиксы строки W, равные её суффиксам, то есть найти грани текста. 2 Для каждой позиции j в слове будет своя величина грани, и величина граней не зависит от подстроки, а зависит только от строки W, поэтому необходимо предварительно вычислить массив (коллекцию) значений граней подстроки W. 2
4. Перед началом работы алгоритма Кнута-Морриса-Пратта необходимо вычислить массив граней подстроки W, а затем прикладывать подстроку к строке со сдвигом, где — текущая позиция в слове, — величина грани слова в позиции. 2

Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно. 4