Алгоритм Кнута-Морриса-Пратта отличается от других методов поиска подстроки тем, что сдвиг подстроки выполняется не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. 1 Перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. 1

Идея алгоритма состоит в том, чтобы не прикладывать подстроку к строке со сдвигом всего в один символ, а максимально увеличить это расстояние, сократив таким образом количество сравнений. 2

В реализации алгоритма Кнута-Морриса-Пратта используется предобработка искомой подстроки, которая заключается в создании префикс-функции на её основе. 1

Таким образом, основное отличие заключается в том, что алгоритм позволяет находить подстроку в строке за количество сравнений, эквивалентное длине строки, даже в самом худшем случае. 12