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

Суббота, 16 февраля 2019
НГУ, ауд. 2128, НГУ, новый корпус

Слайды с лекции

algorithms_2_lecture_160219.pdf

Описание

Строки: основные понятия и обозначения (алфавит, строки, подстроки, суффиксы, префиксы, лексикографический порядок). Задача поиска образца 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).