Что: Лекция
Когда: Суббота, 10 февраля 2018, 14:30–16:05
Где: НГУ, ауд. 2128
Слайды: algorithms_2_lecture_100218.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).

Видео