Алгоритм Кнута — Морриса — Пратта

Алгоритм КМП осуществляет поиск текста по заданному шаблону. В этом поиске сначала компилируется заданный шаблон. Компилируя шаблон, мы пытаемся найти префикс и суффикс строки шаблона. Это поможет в случае несоответствия — не придётся искать следующее совпадение с начального индекса.

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