Андрей Гейн: Это лекция о структуре данных, позволяющей эффективно решать задачи со строками. Мы будем работать с очень длинными текстами и быстро искать в них вхождение подстроки. Субъективная сложность лекции — четыре теты из пяти. Содержание: 5:40 Суффиксное дерево 11:52 Сжатое суффиксное дерево 23:17 Оценка количества вершин и ребёр в сжатом дереве 29:13 Поиск вхождения подстроки, в том числе первого 49:41 Алгоритм построения дерева 57:54 Префиксные ссылки 1:12:20 Алгоритм построения дерева (продолжение) 1:41:03 Лирическое отступление: суффиксный массив, суффиксный автомат 1:43:05 Оценка сложности алгоритма построения дерева 1:56:43 Алгоритмы с линейно-логарифмической и квадратичной сложностью
