ЛКШ-2024, параллель 6. Лекция 10: Алгоритмы на строках. z-функция, префикс-функция, алгоритм КМП.

z-функция. Определение, алгоритм вычисления за линейное время. Применения: поиск подстроки в строке, количество различных подстрок, поиск периода в подстроке. Подсчёт количества подстрок-палиндромов. Алгоритм Манакера. Префикс-функция. Определение, алгоритм вычисления за линейное время. Применения. Поиск подстроки в строке - алгоритм Кнута-Морриса-Пратта. Автомат КМП.