В 2022 году Computer Science Center приостановил набор и обучение
Направления
Курсы
Онлайн-образование
Поступление
О центре
Войти
Направления
Курсы
Онлайн-образование
Онлайн-курсы
Онлайн-программы
Видеозаписи лекций
Поступление
Подать заявку
Памятка
Программа для поступления
Вопросы и ответы
О центре
Преподаватели
Выпускники
Отзывы
Команда
История
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2017
/
Строки. Поиск подстрок
Четверг, 23 марта 2017
Таймс, ауд. 405
Описание
LCP для всех пар за $O(n^2)$
Задачи на хеши
Общая идея #1: любые две строки можно сравнить на равенство за $O(1)$
Общая идея #2: любые две строки можно сравнить на больше/меньше за $O(\log n)$ бинпоиском
Суф.массив за $O(n\log^2 n)$
Z-функция за O(nlogn) хешами
Найти все периоды строки хешами
Количество различных подстрок за [O(n2), O(n)]
Самая длинная общая подстрока, содержащая не более K пробелов за [O(nlogn), O(n)]
Найти максимальную по длине строку, которая входит строку S два раза без наложения [O(nlogn), O(n)]
Задачи на префикс-функцию и Z-функцию, LCP
Найти наибольшую общую подстроку за O(n2) (3 решения: префикс, Z, LCP)
Найти подстроку в тексте с возможностью одной опечатки за O(n) (z-функция с начала, z-функция с конца)
Найти все периоды строки Z-функцией
Найти все периоды строки Prefix-функцией