Конструкция суффиксного массива O(N LogN) — соревновательное программирование 3 Стивен Халим

Сначала вычислите startIndex для каждого уникального рейтинга.

ПРИМЕЧАНИЕ: c[] здесь означает рейтинг, а не только отдельный персонаж.

// compute cumulates of rankings
for (i = sum = 0; i < maxi; i++) {
    int t = c[i]; c[i] = sum; sum += t; 
}

Переупорядочите массив суффиксов, используя только что вычисленные значения startIndices. На основе рейтинга суффикса SA[i]+k.

// shuffle the suffix array if necessary
for (i = 0; i < n; i++){ 
    tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
}

Скопируйте обновленные значения из временного массива.

// copy the updated values back to SA
for (i = 0; i < n; i++){ 
    SA[i] = tempSA[i];
}

Это означает, что суффикс, начинающийся с позиции i, сортируется по рейтингу суффикса на позиции (i+k).

Мы сортируем каждый суффикс длины k по суффиксу длины k на месте i+k. Мы можем это сделать, потому что на предыдущей итерации все суффиксы были отсортированы по длине k.

После этого снова сортируем по первому индексу. Который удерживал рейтинг по размеру k. Поскольку сортировка стабильна, все суффиксы теперь сортируются по длине k*2.

Наш следующий шаг — обновить рейтинг, если два смежных массива суффиксов в рейтинге больше не равны.

for (i = 1; i < n; i++){
    // if same pair => same rank r; otherwise,increase r
    tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;           
}

Если рейтинг для размера k в их startIndex одинаков, и рейтинг в их startIndex+k такой же. Тогда ранжирование в startIndex такое же, как и для размера k*2.

Это также должно объяснить следующее:

if (RA[SA[n-1]] == n-1) break; // nice optimization trick

Это означает, что в этот момент все рейтинги для текущего размера уникальны. Таким образом, все суффиксы также уникальны, и дальнейшая сортировка не требуется.

Пошаговый пример:

  a   b   c   x   a   b   c   d 
--------------------------------INIT-
  0   1   2   3   4   5   6   7 // SA
 97  98  99 120 97  98  99  100 // RA
---------------------------------K=1-
  0   2   5   7   1   3   4   6 // SA
  0   1   2   4   0   1   2   3 // RA
---------------------------------K=2-
  1   3   5   7   0   2   4   6 // SA
  1   3   5   7   0   2   4   6 // RA

Пример countintSort для шага K=1:

// count frequencies
c['a']=2;
c['b']=2;
c['c']=2;
c['d']=1;
c['x']=1;

// switch them to startindices
c['a']=0;
c['b']=2;
c['c']=4;
c['d']=6; // e.g. in total there are 6 suffixes smaller than starting with d (2 x a, 2 x b, 2 x c)
c['x']=7;

// determine the new SA position
tempSA[c[rank(SA[i]+k)]++] = SA[i];
// decomposing first iteration
tempSA[c[rank(SA[0]+k)]++] = SA[0]; // i = 0
tempSA[c[rank(SA[0]+1)]++] = SA[0]; // k = 1
tempSA[c[rank(1)]++] = 0; // SA[0] = 0
tempSA[c['b']++] = 0; // rank(1) = 'B'
tempSA[2] = 0; // c['b']=2 => 2++ = 3

Другими словами: поместите текущий первый массив суффиксов в startIndex массива суффиксов, который начинается через k мест после. И увеличьте этот startIndex на единицу, чтобы следующее вхождение не переопределялось.

// all other iterations resulting in:
tempSA[0] = 7 // d (sorted by EMPTY)
tempSA[1] = 3 // x (sorted by a)
tempSA[2] = 0 // a (sorted by b)
tempSA[3] = 4 // a (sorted by b)
tempSA[4] = 1 // b (sorted by c)
tempSA[5] = 5 // b (sorted by c)
tempSA[6] = 6 // c (sorted by d) 
tempSA[7] = 2 // c (sorted by d)

// last step is simply copying those values to SA (I suppose you know why this is)

Это все, что я могу вам дать, если у вас все еще есть проблемы, попробуйте пройти это с помощью отладчика или распечатать промежуточные результаты, если у вас есть сомнения.