Алгоритм поиска строк Кнута Морриса Пратта (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. Другими словами, мы сдвигаем строку шаблона так, чтобы её первый символ совпадал со следующим символом в тексте. Это гарантирует, что каждый символ в тексте будет прочитан не более двух раз.