Лекция 4. Суффиксный массив

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) с их помощью.