Понимание реализации алгоритма DC3/Skew для создания линейного времени массива суффиксов

Рассмотрим следующий пример, где длина входных данных равна n=13:

 STA | CKO | WER | FLO | W

По коду: n0 = (n + 2)/3, n1 = (n + 1)/3, n2 = n/3; => Как были получены эти инициализации?

Обратите внимание, что количество троек i mod3 = 0 равно n/3, если n mod3 = 0, и n/3+1 в противном случае (если n mod3 = 1 или n mod3 = 2). В текущем примере n/3 = 4, но поскольку последняя тройка 'W' неполная, она не учитывается при целочисленном делении. «Хитрость» для непосредственного выполнения этого вычисления заключается в использовании (n+2)/3. Фактически, если n mod3 = 0, то результат целочисленного деления (n+2)/3 и n/3 будет одинаковым. Однако если n mod3 = 1 или 2, то результатом (n+2)/3 будет n/3+1. То же самое относится к n1 и n2.

По коду: n02 = n0 + n2; s12 = [n02] ==> Как появился n02? Должно быть n12, т.е. n1 + n2. В соответствии с кодом: for (int i = 0, j = 0; i ‹ n + (n0 - n1); i++) заполните s12 такими тройками, что i%3 != 0; => Почему цикл for выполняется n + (n0 - n1) раз? Это должно быть просто n1 + n2. Не должно быть?

Оба вопроса имеют один и тот же ответ. В нашем примере у нас будет такой буфер B12:

B12 = B1 U B2 = {TA KO ER LO}

Таким образом, вы должны сначала отсортировать суффиксы и получить массив суффиксов B12, который имеет 8 элементов. Чтобы перейти к шагу слияния, нам сначала нужно вычислить массив суффиксов B0, который получается путем сортировки кортежей (B0(i),rank(i+1))... Но этот конкретный случай, когда последний триплет имеет только один элемент (W) имеет проблему, потому что rank(i+1) не определен для последнего элемента B0:

B0 = {0,3,6,9,12}

который отсортирован по алфавиту, приводит к

SA0 = {3, 9, 0, ?, ?}

Поскольку индексы 6 и 12 содержат «W», недостаточно отсортировать по алфавиту, нам нужно проверить, что идет первым в таблице рангов, поэтому давайте проверим ранг их суффиксов.. о, подождите! ранг(13) не определен!

И именно поэтому мы добавляем фиктивный 0 к последней тройке входных данных, когда последняя тройка содержит только один элемент (если n mod3 = 0). Таким образом, размер B12 равен n0+n2, независимо от размера n1, и нужно добавить дополнительный элемент к B12, если B0 больше, чем B1 (в этом случае n0-n1 = 1).

Надеюсь было понятно.