Что: Семинар
Когда: Четверг, 23 марта 2017, 20:00–21:20
Где: Таймс, ауд. с чёрными досками

Описание

  • 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-функцией