Лекция 5. Суффиксный массив (продолжение)

Построение SA для строки S за O(N + C), алгоритм Kaerkainen-Sanders. Суперсимволы (тройки), формирование и нумерация супералфавита. Строка T из суперсимволов длины 2/3 * N и рекурсивный вызов SA. Классы суффиксов S по остатку от деления начальной позиции на 3: =0, =1, =2. Соответствие суффиксов T и суффиксов S классов =0 и =1. Возможность сравнения суффиксов классов =0 и =1 между собой за O(1). Сравнение суффиксов из класса =2 с остальными за O(1). Порядок суффиксов классов =0 и =1 (по SA строки T). Определение порядка классов =2 (radix sort). Слияние порядков за линейное время. Время работы O(N). LCP-структура. Определение lcp-массива. Сведение LCP двух суффиксов к RMQ на lcp-массиве. Оптимальное решение (O(N) времени на предподсчёт, O(1) времени на запрос). Вычисление lcp-массива. Порядок: ISA[p] для 1..n. Свойство: lcp[ISA[p+1]] >= lcp[ISA[p]] - 1. Простой алгоритм за O(N)