Семинар 4. Недетерминированные автоматы

Задача поиска максимальной общей подстроки. Сведение к поиску макс. 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-НКА: состояние ДКА = множество состояний (аналогично алгоритму проверки слова). Экспоненциальное увеличение кол-ва состояний, пример.