Алгоритм поиска строк Кнута Морриса Пратта (KMP) — руководство с функцией отказа на Java

Описание: В этом руководстве объясняется, как работает алгоритм сопоставления с образцом Кнута-Морриса-Пратта (KMP). Для наглядной визуализации базовой концепции используются анимированные примеры. Затем обсуждается исходный код реализации, написанной на Java, и её время выполнения.

Алгоритм состоит из двух частей. Первая часть создаёт «функцию отказа», которая представляет собой массив, содержащий самые длинные префиксы, встречающиеся в строке шаблона. Основной алгоритм использует этот массив длин префиксов для вычисления смещения строки шаблона вперёд.

Исходный код, написанный на Java:
https://bitbucket.org/StableSort/play...

Реализация основана на псевдокоде, взятом из Википедии:
https://en.wikipedia.org/wiki/Knuth%E...

БЫСТРОЕ СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ В СТРОКАХ
ДОНАЛЬД Э. КНУТ, ДЖЕЙМС Х. МОРРИС-МЛАДШИЙ И ВОН Р. ПРАТТ
https://pdfs.semanticscholar.org/4479...

Автор и озвучка: Андре Виолентьев

-------------------------------------------------------------------------------------------------------------------------------------------------------------
Опечатка (благодаря @Achyut Sapkota):
Моя анимация на 6:04 должна была сместиться не на 2, а на 3 символа. Кстати, в этом месте мы также увеличили бы указатель в тексте до следующего символа. Исходный код (см. выше) верен — как только мы достигаем нулевого индекса массива prefixLen, в котором хранится -1, мы увеличиваем указатели как текста, так и строки шаблона:
p = prefixLen[p];
if (p 'less than' 0) {
t++;
p++;
}
В приведённом выше примере при сдвиге на 3 символа мы фактически выходим за пределы строки шаблона. На иллюстрациях показано, что первый символ, «a», находится на индексе 1 массива prefixLen (а не на индексе 0, что, вероятно, и вызывает путаницу, поскольку в большинстве языков программирования индексация строк начинается с 0). Итак, формула работает, просто при обнаружении выхода за пределы строки мы сбрасываем указатель строки шаблона на первый символ и увеличиваем указатель текста на 1. Другими словами, мы сдвигаем строку шаблона так, чтобы её первый символ совпадал со следующим символом в тексте. Это гарантирует, что каждый символ в тексте будет прочитан не более двух раз.