Лекция 2. Префикс-функция, поиск бора (Алгоритмы и структуры данных, часть 2)

Алгоритм Кнута-Морриса-Пратта: идея, время работы. Префикс-суффиксы (borders), максимальный из них, множество всех префикс-суффиксов строки. Префикс-функция строки. Алгоритм вычисления префикс-функции, время работы. Префикс-функция строки P#T, предподсчёт и поиск КМП. Много образцов: время работы. Бор (trie), вставка слов в бор. Порождённый образцами бор, пометки вершин бора. Определение функции отката FF(a). Проход по тексту с отслеживанием вершины в боре, время работы. Определение найденных вхождений образцов, время работы. Построение функции FF, порядок обхода вершин (в ширину), время работы. Зависимость затрат времени и памяти от размера алфавита: использование массива, списка, дерева поиска для хранения переходов. Лекция №2 в курсе "Алгоритмы и структуры данных, часть 2", весна 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: https://goo.gl/71Vf1G Все видео курса по порядку: https://goo.gl/b8KQcs