Лекция 1. Строки. Z-функция

Строки: основные понятия и обозначения (алфавит, строки, подстроки, суффиксы, префиксы, лексикографический порядок). Задача поиска образца P в тексте T. Longest Common Prefix, Z-функция. Точный поиск подстроки через Z-функцию от P#T. sentinel-символ.

Алгоритм вычисления Z-функции за линейное время. Поиск через Z-функцию с O(P) дополнительной памяти, отделение предподсчёта от поиска. Расстояние редактирования ED. Неточный поиск подстроки (ED <= 1). Реализация поиска через Z-функции от P#T и rev(P)#rev(T). Использование Z-функции для вычисления LCP вида LCP(A, suffix(B)) за O(1).