Ответ 1

Обзор

Это алгоритм O (n log n) для построения массива суффиксов (вернее, это было бы, если бы вместо ::sort была использована сортировка двухпроходного ковша).

Он работает, сначала сортируя 2 грамма ^(*) затем 4-граммы, затем 8-граммы и т.д. исходной строки S, поэтому в i-й итерации, мы сортируем 2 ⁱ -граммы. Очевидно, что для таких итераций может быть не более log ₂ (n), и трюк заключается в том, что сортировка 2 ⁱ -грамм на i-м шаге облегчается путем создания что каждое сравнение двух 2 ⁱ -грамм выполняется в O (1) раз (а не O (2 ⁱ)).

Как это делается? Ну, в первой итерации сортирует 2-граммовые (ака-биграмсы), а затем выполняет так называемое лексикографическое переименование. Это означает, что он создает новый массив (длиной n), который хранит для каждого битрама свой ранг в сортировке bigram.

Пример для лексикографического переименования: Скажем, у нас есть отсортированный список некоторых биграмм {'ab','ab','ca','cd','cd','ea'}. Затем мы присваиваем ранги (то есть лексикографические имена), переходя слева направо, начиная с ранга 0 и увеличивая ранг всякий раз, когда встречаемся с новыми изменениями bigram. Таким образом, мы назначаем ранги:

ab : 0
ab : 0   [no change to previous]
ca : 1   [increment because different from previous]
cd : 2   [increment because different from previous]
cd : 2   [no change to previous]
ea : 3   [increment because different from previous]

Эти ранги известны как лексикографические имена.

Теперь, в следующей итерации, мы сортируем 4 грамма. Это связано с большим количеством сравнений между различными 4-граммами. Как мы сравниваем два 4-граммовых? Ну, мы могли бы сравнить их по характеру. Это было бы до 4 операций за сравнение. Но вместо этого мы сравниваем их, просматривая ряды двух биграмм, содержащихся в них, используя таблицу рангов, сгенерированную на предыдущих шагах. Этот ранг представляет собой лексикографический ранг из предыдущей 2-граммовой сортировки, поэтому, если для любого данного 4-грамма его первый 2-грамм имеет более высокий ранг, чем первые 2 грамма другого 4-грамма, то он должен быть лексикографически большим где-то в первых двух символах. Следовательно, если для двух 4-граммов ранг первого 2-грамма идентичен, они должны быть одинаковыми в первых двух символах. Другими словами, для сравнения всех четырех символов двух 4-граммов достаточно двух поисков в таблице рангов.

После сортировки мы снова создаем новые лексикографические имена, на этот раз для 4-граммов.

В третьей итерации нам нужно сортировать по 8 граммам. Опять же, два обзора в таблице лексикографического ранжирования с предыдущего шага достаточны для сравнения всех 8 символов двух заданных 8 грамм.

И так далее. Каждая итерация i имеет два шага:

• Сортировка по 2 ⁱ -грамм, используя лексикографические имена из предыдущей итерации, чтобы обеспечить сравнение в 2 этапа (то есть время O (1))

• Создание новых лексикографических имен

Повторяем это до тех пор, пока все 2 ⁱ -граммы не будут различны. Если это произойдет, мы закончили. Откуда мы знаем, все ли разные? Ну, лексикографические имена - это возрастающая последовательность целых чисел, начиная с 0. Так что если наивысшее лексикографическое имя, сгенерированное на итерации, такое же, как n-1, то каждый 2 ⁱ -gram должен был быть учитывая его собственное, отличное лексикографическое имя.

Реализация

Теперь посмотрим на код, чтобы подтвердить все это. Используемые переменные: sa[] - массив суффикса, который мы строим. pos[] - таблица поиска ранга (т.е. содержит лексикографические имена), в частности, pos[k] содержит лексикографическое имя k -th m-gram предыдущего шага. tmp[] - вспомогательный массив, используемый для создания pos[].

Я дам дальнейшие объяснения между строками кода:

void buildSA()
{
    N = strlen(S);

    /* This is a loop that initializes sa[] and pos[].
       For sa[] we assume the order the suffixes have
       in the given string. For pos[] we set the lexicographic
       rank of each 1-gram using the characters themselves.
       That makes sense, right? */
    REP(i, N) sa[i] = i, pos[i] = S[i];

    /* Gap is the length of the m-gram in each step, divided by 2.
       We start with 2-grams, so gap is 1 initially. It then increases
       to 2, 4, 8 and so on. */
    for (gap = 1;; gap *= 2)
    {
        /* We sort by (gap*2)-grams: */
        sort(sa, sa + N, sufCmp);

        /* We compute the lexicographic rank of each m-gram
           that we have sorted above. Notice how the rank is computed
           by comparing each n-gram at position i with its
           neighbor at i+1. If they are identical, the comparison
           yields 0, so the rank does not increase. Otherwise the
           comparison yields 1, so the rank increases by 1. */
        REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);

        /* tmp contains the rank by position. Now we map this
           into pos, so that in the next step we can look it
           up per m-gram, rather than by position. */
        REP(i, N) pos[sa[i]] = tmp[i];

        /* If the largest lexicographic name generated is
           n-1, we are finished, because this means all
           m-grams must have been different. */
        if (tmp[N - 1] == N - 1) break;
    }
}

О функции сравнения

Функция sufCmp используется для сравнения двух (2 * разрывов) -грамм лексикографически. Таким образом, на первой итерации сравниваются битрамы, во второй итерации - 4 грамма, затем 8 грамм и так далее. Это контролируется gap, который является глобальной переменной.

Наивная реализация sufCmp будет следующей:

bool sufCmp(int i, int j)
{
  int pos_i = sa[i];
  int pos_j = sa[j];

  int end_i = pos_i + 2*gap;
  int end_j = pos_j + 2*gap;
  if (end_i > N)
    end_i = N;
  if (end_j > N)
    end_j = N;

  while (i < end_i && j < end_j)
  {
    if (S[pos_i] != S[pos_j])
      return S[pos_i] < S[pos_j];
    pos_i += 1;
    pos_j += 1;
  }
  return (pos_i < N && pos_j < N) ? S[pos_i] < S[pos_j] : pos_i > pos_j;
}

Это сравнило бы (2 * gap) -грамму в начале i-го суффикса pos_i:=sa[i] с тем, которое было найдено в начале j-го суффикса pos_j:=sa[j]. И он будет сравнивать их по характеру, то есть сравнивать S[pos_i] с S[pos_j], затем S[pos_i+1] с S[pos_j+1] и так далее. Он продолжается до тех пор, пока символы идентичны. Как только они отличаются, он возвращает 1, если символ в i-м суффиксе меньше, чем символ в j-м суффиксе, 0 в противном случае. (Обратите внимание, что return a<b в функции, возвращающей int означает, что вы возвращаете 1, если условие истинно, и 0, если оно ложно.)

Сложное условие поиска в return-statement относится к случаю, когда одна из (2 * gap) -грамм находится в конце строки. В этом случае либо pos_i, либо pos_j достигнет n до того, как будут сопоставлены все (2 * пробелы) символы, даже если все символы до этой точки идентичны. Затем он вернет 1, если i-й суффикс находится в конце, и 0, если j-й суффикс находится в конце. Это правильно, потому что, если все символы идентичны, более короткий размер лексикографически меньше. Если pos_i достиг конца, i-й суффикс должен быть короче j-го суффикса.

Ясно, что эта наивная реализация - O (зазор), т.е. ее сложность линейна по длине (2 * gap) -грамм. Однако функция, используемая в вашем коде, использует лексикографические имена, чтобы довести это до O (1) (в частности, до двух сравнений):

bool sufCmp(int i, int j)
{
  if (pos[i] != pos[j])
    return pos[i] < pos[j];
  i += gap;
  j += gap;
  return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}

Как вы можете видеть, вместо поиска отдельных символов S[i] и S[j] мы проверяем лексикографический ранг i-го и j-го суффикса. Лексикографические ранги вычислялись в предыдущей итерации для грамм-грамм. Итак, если pos[i] < pos[j], то i-й суффикс sa[i] должен начинаться с графа-пробела, который лексикографически меньше грамм-грамма в начале sa[j]. Другими словами, просто просмотрев pos[i] и pos[j] и сравнивая их, мы сравнили первые пробельные символы двух суффиксов.

Если ряды идентичны, мы продолжаем, сравнивая pos[i+gap] с pos[j+gap]. Это то же самое, что и сравнение следующих заглавных символов (2 * gap) -грамм, т.е. Второй половины. Если ряды снова являются indentical, две (2 * gap) -граммы являются indentical, поэтому мы возвращаем 0. В противном случае мы возвращаем 1, если i-й суффикс меньше j-го суффикса, 0 в противном случае.

Пример

Следующий пример иллюстрирует работу алгоритма и демонстрирует, в частности, роль лексикографических имен в алгоритме сортировки.

Строка, которую мы хотим отсортировать, abcxabcd. Для создания массива суффиксов требуется три итерации. На каждой итерации я покажу S (строка), sa (текущее состояние массива суффиксов) и tmp и pos, которые представляют собой лексикографические имена.

Сначала мы инициализируем:

S   abcxabcd
sa  01234567
pos abcxabcd

Обратите внимание, как лексикографические имена, которые первоначально представляют лексикографический ранг униграмм, просто идентичны символам (т.е. самим униграммами).

Первая итерация:

Сортировка sa, используя битрамы в качестве критерия сортировки:

sa  04156273

Первые два суффикса - 0 и 4, потому что это позиции bigram 'ab'. Затем 1 и 5 (позиции биграма 'bc'), затем 6 (bigram 'cd'), затем 2 (bigram 'cx'). затем 7 (неполный bigram 'd'), затем 3 (bigram 'xa'). Ясно, что позиции соответствуют порядку, основанному исключительно на символах bigrams.

Создание лексикографических имен:

tmp 00112345

Как описано, лексикографические имена назначаются как возрастающие целые числа. Первые два суффикса (оба, начинающиеся с bigram 'ab'), получают 0, следующие два (оба начинаются с bigram 'bc') получают 1, затем 2, 3, 4, 5 (каждый другой биграмм).

Наконец, сопоставим это в соответствии с позициями в sa, чтобы получить pos:

sa  04156273
tmp 00112345
pos 01350124

(Создается способ pos: Пройдите sa слева направо и используйте запись для определения индекса в pos. Используйте соответствующую запись в tmp, чтобы определить значение для этот индекс. Итак, pos[0]:=0, pos[4]:=0, pos[1]:=1, pos[5]:=1, pos[6]:=2 и т.д. Индекс приходит от sa, значение от tmp.)

Вторая итерация:

Мы сортируем sa снова, и снова мы смотрим на битрамы из pos (каждый из которых представляет последовательность из двух биграмм исходной строки).

sa  04516273

Обратите внимание, как позиция 1 5 переключилась по сравнению с предыдущей версией sa. Раньше было 15, теперь это 51. Это связано с тем, что в предыдущей итерации биграм в pos[1] и bigram at pos[5] был идентичным (оба bc), но теперь bigram at pos[5] is 12, а bigram at pos[1] - 13. Поэтому позиция 5 предшествует позиции 1. Это связано с тем, что теперь лексикографические имена представляют собой биграмм исходной строки: pos[5] представляет bc и pos[6] представляет 'cd'. Итак, вместе они представляют bcd, а pos[1] представляет bc и pos[2] представляет cx, поэтому вместе они представляют bcx, который действительно лексикографически больше, чем bcd.

Опять же, мы генерируем лексикографические имена, просматривая текущую версию sa слева направо и сравнивая корреляционные биграммы в pos:

tmp 00123456

Первые две записи по-прежнему идентичны (оба значения 0), поскольку соответствующие биграммы в pos являются как 01. Остальное представляет собой строго возрастающую последовательность целых чисел, так как все остальные битрамы в pos уникальны.

Мы выполняем сопоставление с новым pos по-прежнему (принимая индексы от sa и значения от tmp):

sa  04516273
tmp 00123456
pos 02460135

Третья итерация:

Мы сортируем sa снова, беря битраграммы pos (как всегда), которые теперь представляют собой последовательность из четырех биграмм исходной строки.

sa  40516273

Вы заметите, что теперь первые две записи имеют переключаемые позиции: 04 стал 40. Это связано с тем, что bigram at pos[0] составляет 02, а тот, который находится в pos[4], равен 01, последний, очевидно, лексикографически меньше. Глубокая причина в том, что эти два представляют abcx и abcd соответственно.

Создание лексикографических названий дает:

tmp 01234567

Все они разные, т.е. самый высокий - 7, который n-1. Итак, мы закончили, потому что сортировка теперь основана на m-граммах, которые все разные. Даже если мы продолжим, порядок сортировки не изменится.

Предложение по улучшению

Алгоритм, используемый для сортировки 2 ⁱ -грамм на каждой итерации, представляется встроенным sort (или std::sort). Это означает, что это сортировка, которая принимает O (n log n) время в худшем случае на каждой итерации. Так как в худшем случае существуют логические n-итерации, это делает его алгоритмом O (n (log n) ²). Однако сортировка могла выполняться с использованием двух проходов сортировки в виде ведра, поскольку ключи, которые мы используем для сравнения сортировки (то есть лексикографические имена предыдущего шага), образуют возрастающую целую последовательность. Таким образом, это может быть улучшено до реального алгоритма O (n log n) -time для сортировки суффиксов.

Примечание

Я считаю, что это оригинальный алгоритм построения массива суффикса, который был предложен в статье 1992 года ссылкой Manber and Myers (на Google Scholar, это должно быть первый удар, и у него может быть ссылка на PDF файл). Это (в то же время, но независимо от работы Gonnet и Baeza-Yates) заключалось в том, что введенные массивы суффиксов (также называемые пат-массивами в то время) в качестве структуры данных, интересной для дальнейшего изучения.

Современные алгоритмы построения массива суффиксов - это O (n), поэтому выше уже не лучший доступный алгоритм (по крайней мере, не в плане теоретической, наихудшей сложности).

Сноски

^(*) Через 2-грамм я подразумеваю последовательность из двух последовательных символов исходной строки. Например, когда S=abcde является строкой, то ab, bc, cd, de являются 2-граммами S. Аналогично, abcd и bcde являются 4-граммами. Как правило, m-грамм (для положительного целого числа m) представляет собой последовательность m последовательных символов. 1 грамм также называются униграммами, 2 грамма называются битрамами, 3 грамма - триграммами. Некоторые люди продолжают тетраграммы, пентаграммы и т.д.

Обратите внимание, что суффикс S, который начинается и позиция i, является (n-i) -граммой S. Кроме того, каждый m-грамм (для любого m) является префиксом одного из суффиксов S. Поэтому сортировка m-грамм (для максимально возможного m) может быть первым шагом на пути сортировки суффиксов.

Ответ 2

Как вы выбрали Codeforces для этого, я считаю, что вы тоже знакомы с Topcoder:) Пожалуйста, проверьте приведенную ниже ссылку и у нее есть еще несколько ссылок. Я видел, как многие люди изучали массив Суффикса только из этих ссылок.

Ссылка TopCoder здесь

И кусок золота для программистов. Я узнал массив Суффикса из этот документ