Сжатый суффиксный массив: различия между версиями

Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения <math>A^{-1} [j]</math>. Это обратное значение используется для извлечения произвольных подстрок текста T[p, r], вначале применяя <math>i = A^{-1}[p]</math>, а затем, как и прежде, продолжая извлекать r — p + 1 первых символов суффикса T[A[i], n]. Эта возможность превращает сжатый суффиксный массив в самоиндексируемый:

'''Теорема 3 (Садаканэ [10]). Сжатый суффиксный массив Садаканэ — это самоиндекс, занимающий <math>\frac{1}{\epsilon}nH_0 + O(n \; log \; log \; \sigma)</math> бит и поддерживающий извлечение значений <math>A[i]</math> и <math>A^{-1}[j]</math> за время <math>O(log^{\epsilon} \; n)</math>, подсчет вхождений шаблона за время <math>O(m \; log \; n)</math> и отображение любой подстроки T длины <math>\ell</math> за время <math>O(\ell + log^{\epsilon} \; n)</math>, где <math>0 < \epsilon < 1</math> — произвольная константа.'''