Семинар 4. Недетерминированные автоматы (Алгоритмы и структуры данных, часть 2)

Задача поиска максимальной общей подстроки. Сведение к поиску макс. LCP. Решение с полиномиальными хешами: бинарный поиск по ответу, выписывание хешей, поиск хеша, который встречается всюду. Время работы O(N log N). Безопасный алгоритм: разрешение коллизий подстрок. Оценка дополнительного времени работы в среднем для разрешения коллизий. Решение с суффиксным деревом: считаем для каждой вершины наличие в поддереве вершин каждого типа. Решение варианта с K строками за O(N K).

Недетерминированный КА, eps-переходы. Механика работы автоматов. Недетерминированность = параллельные миры. Проверка слова. ДКА: O(1) памяти и O(1) времени на символ. НКА: метод динам. прогр. (O(N) памяти, O(M) времени на символ). eps-НКА: замыкание по eps-переходами, серия обходов графа за линейное время (O(N) памяти, O(M) времени на символ). Построение ДКА по eps-НКА: состояние ДКА = множество состояний (аналогично алгоритму проверки слова). Экспоненциальное увеличение кол-ва состояний, пример.
Семинар №4 в курсе "Алгоритмы и структуры данных, часть 2", весна 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов
Страница лекции на сайте CS центра: https://goo.gl/K4rXih
Все видео курса по порядку: https://goo.gl/b8KQcs