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

LCP-структура. Суффиксное дерево для S = A$B#. Сведение LCP суффиксов A и B к LCA вершин суффиксного дерева S. Суффиксный массив (SA). Определение, обратный суфф. масс. (ISA). Две нумерации суффиксов: по позиции в строке, по рангу в суфф. массиве. Поиск образца при помощи SA. Бинарный поиск за O(P log T). Хранение LCP с образцом на границах отрезка. Использование LCP среднего и граничных суффиксов. Почти полное определение топологии бора с левым, правым, средним суффиксом и образцом, посимвольное сравнение в проблемном случае. Время работы O(P + log T). Построение SA. Добавление sentinel-ов после конца строки. Разметка (labelling) множества строк в порядке сортировки. Идея: строим разметку phi_k для всех подстрок длины 2^k, k = 0..logN. Начальная разметка phi_0 - сортировка подсчётом. Переход от разметки phi_k к разметке phi_{k+1} - цифровая сортировка пар рангов. Время работы O(N log N + C). Сохранение разметок phi_k в построении SA (всего O(N log N) памяти). Вычисление LCP двух суффиксов за O(log N) с их помощью.
Лекция №4 в курсе "Алгоритмы и структуры данных, часть 2", весна 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов

[minmanr]

13:45 Лексикографический порядок строк. Выполняется сравнение символов a < b, но не обговаривается, что подразумевается под этим. Вероятно, в алфавите задан порядок всех символов?