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

'''Определение 1.''' Пусть дан суффиксный массив A[1, n]. Функция <math>\Psi : [1, n] \to [1, n]</math> определяется таким образом, что для всех <math>1 \le i < n</math> выполняется соотношение <math>A[\Psi(i)] = A[i] + 1</math>. Исключением является A[1] = n, в этом случае имеет место <math>A[\Psi(l)] = 1</math>, так что функция <math>\Psi</math> является перестановкой.

Гросси и Виттер используют иерархическую декомпозицию А, основанную на 4>2. рассмотрим первый уровень этой иерархической декомпозиции. Пусть A0 = A – исходный суффиксный массив. Битовый вектор B°[1;n] определен таким образом, что B°[i] = 1, если A[i] четно. Также пусть ^[l. dn/2e ] содержит последовательность значений 4>{i) для аргументов i, где B°[i] = 0. Наконец, пусть A1[1; BN/2C] будет подпоследовательностью A0[1; n], образованной четными значениями A0[i], деленными на 2.