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

Поиск подстроки в строке   7 января 2012  Автор статьи:  

Задан текст, или массив. Нужно определить вхождение образца(строки или подмассива) в текст.

Алгоритм решения

Данный алгоритм основывается на вычислении префикс функции строки. Префикс функция- это наибольшая длина подстроки, которая заканчивается в позиции i, и совпадает с началом строки. Таким образом, если научиться считать префикс функцию, то нахождение всех вхождений станет тривиальной задачей. Для этого достаточно склеить массив байт сигнатуры с массивом секции кода, поставив между ними искусственный разделитель. Обычно для этого используют символ, который не встречается в алфавите строк, но т.к в данной статье для усложнения речь идет о массиве байт, то все байты чисто теоретически могут присутствовать в ней, поэтому я просто добавил в код искусственную проверку для этого символа-разделителя.

Для вычисления префикс функции очевиден факт, что значение от i+1 префикс функции не превосходит значение от i больше чем на 1.Иначе бы мы могли бы на предыдущем шаге выбрать другую подстроку и увеличить значение префикс функции. Таким образом префикс функция может либо уменьшиться, либо остаться неизменной, либо увеличится на единицу. Дальше хотелось бы избежать явных сравнений. Для этого нужно по максимуму использовать информацию на предыдущем шаге. Если следующий символ строки равен символу, стоящему в строке под номером, равным предыдущему значению префикс функции, тогда значение префикс функции достаточно увеличить на единицу в сравнение с предыдущим. На основе этих двух фактов можно понять, что значение префикс функции уменьшается следующим образом. Если значение больше нуля и символ с номером соответствующим значению не равен символу соответствующему номеру шага, то значение следует положить значению префикс функции на предыдущем шаге. Теперь осталось проверить увеличение на единицу префикс функции, которое было описано выше и значение префикс функции на данном шаге посчитано. Осталось добавить, что значение на нулевом шаге равно нулю и алгоритм полностью готов.

Алгоритм Кнута-Морриса-Пратта работает за время O(m+n). Где m- длина текста или массива байт, а n- длина образца.

Научиться программировать

  • на Delphi

  • на Java

  • на C++