В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2018
/

Семинар 1. LCP, поиск палиндромов, ДКА

Суббота, 10 февраля 2018
НГУ, ауд. 2128, НГУ, новый корпус
Список тем / 23 записи
    1.
    Строки. Z-функция
    2.
    Семинар 1. LCP, поиск палиндромов, ДКА
    3.
    Префикс-функция, поиск бора.
    4.
    Семинар 2. Поиск тандемных повторов, Ахо-Корасик
    5.
    Суффиксное дерево
    6.
    Семинар 3. Эквивалентность автоматов
    7.
    Суффиксный массив
    8.
    Семинар 4. Недетерминированные автоматы.
    9.
    Семинар 5. Регулярные выражения
    10.
    Семинар 6. Контекстно-свободные грамматики
    11.
    Суффиксный массив (продолжение)
    12.
    Преобразование Барроуза-Уилера
    13.
    Приближённый поиск подстроки
    14.
    Семинар 7. Контекстно-свободные грамматики (алгоритмы)
    15.
    Графы, обход в ширину, обход в глубину
    16.
    Семинар 8. Разбор КС-грамматики
    17.
    Обход в глубину (продолжение)
    18.
    Кратчайшие пути
    19.
    Семинар 10. Остовные деревья, сжатие компонент
    20.
    Кратчайшие пути (продолжение)
    21.
    Семинар 11. NP-задачи и игры на графах
    22.
    Потоки
    23.
    Семинар 12. Потоки минимальной стоимости

Приложенные файлы

contest_nsk.pdf howto_nsk2.pdf

Описание

Вычисление всех LCP(suffix(A), suffix(B)) за O(M*N) простой динамикой.

Полиномиальное хеширование. Вычисление хеша от подстроки за O(1) с предподсчётом степеней основания. Предположение об идеальности хеша для всех встречающихся в задаче строк (обычно это все подстроки входных строк). Определение равенства подстрок за O(1). Вычисление LCP вида LCP(suffix(A), suffix(B)) за O(log N) бинарным поиском. Проблема разрешения коллизий.

Поиск подстрок-палиндромов. Тривиальное решение за O(N^3). Простое решение за O(N^2). Размер ответа O(N^2). Идея: возвращаем ответ в сжатом виде. Четный(*) и нечётный случаи. Сжатый вид: для каждого i ищем Q(i) - длину макс. палиндрома с центром в i. Вычисление Q слева направо. Использование блока. Хранение блока с макс. правой границей. (Алгоритм аналогичен алгоритму поиска Z-функции).

Детерминированный конечный автомат (ДКА). Смысл, картинка, определение. Конфигурации и такты. Распознаваемый язык L(A). Слив. Примеры: натуральные числа; кратные D; палиндромы (неуспешно).