4551
правка
Сжатый суффиксный массив: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
Тогда A = | Тогда <math>A = A_0</math> может быть представлен с использованием только <math>\Psi_0, B^0</math> и <math>A_1</math>. Чтобы извлечь A[i], сначала проверим, выполняется ли <math>B^0[i] = 1</math>. Если это так, то A[i] было разделено на 2 где-то в <math>A_1</math>. Точное положение зависит от того, сколько единиц встречается в <math>B^0</math> до позиции i, обозначенной как <math>rank(B^0, i)</math>, т. е. <math>A[i] = 2 \cdot A_1[rank_1(B^0, i)]</math>. Если B°[i] = 0, то A[i] является нечетным и не представлен в <math>A_1</math>. Однако в этом случае элемент <math>A[i] + 1 = A[\Psi(i)]</math> должен быть четным и, таким образом, должен быть представлен в <math>A_1</math>. Так как <math>\Psi_0</math> содержит только значения <math>\Psi</math>, у которых <math>B^0[i] = 0</math>, из этого следует, что <math>A[\Psi(i)] = A[\Psi_0[rank_0(B^0, i)]]</math>. После вычисления <math>A[\Psi(i)]</math> (для четных <math>\Psi(i)</math>) элементарно получаем <math>A[i] = A[\Psi(i)] - 1</math>. | ||
