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

Первое решение проблемы предложили Гросси и Виттер [3], использовавшие свойство регулярности суффиксного массива посредством функции <math>\Psi</math>:

Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на <math>\Psi</math> ''//далее приводится описание, близкое к изложенному в [9]//''. рассмотрим первый уровень этой иерархической декомпозиции. Пусть <math>A_0 = A</math> – исходный суффиксный массив. Битовый вектор <math>B^0 [1, n]</math> определен таким образом, что <math>B^0 [i] = 1</math> в том и только том случае, если A[i] четно. Кроме того, пусть <math>\Psi_0 [1, \lceil n/2 \rceil ]</math> содержит последовательность значений <math>\Psi(i)</math> для тех аргументов i, для которых <math>B^0[i] = 0</math>. Наконец, пусть <math>A_1 [1, \lfloor n/2 \rfloor ]</math> будет подпоследовательностью <math>A_0 [1, n]</math>, образованной четными значениями <math>A_0[i]</math>, деленными на 2.