E103. Suffix array
Источник: e-maxx.ru/algo, страница PDF 307.
Дана string
длины
.
-ым суффиксом строки называется substring
,
.
Тогда суффиксным arrayом строки
называется перестановка индексов суффиксов
,
, которая задаёт порядок суффиксов в порядке лексикоgraphической
сортировки. Иными словами, нужно выполнить сортировку всех суффиксов заданной строки.
НаExample, для строки
Suffix array будет равен:
Построение за
Строго говоря, описываемый ниже Algorithm будет выполнять сортировку не суффиксов, а циклических сдвигов строки. Однако из этого Algorithmа легко получить и Algorithm сортировки суффиксов: достаточно приписать в конец строки произвольный символ, который заведомо меньше любого символа, из которого может состоять string (наExample, это может быть доллар или шарп; в языке C в этих целях можно использовать уже имеющийся нулевой символ). Сразу заметим, что поскольку мы сортируем циклические сдвиги, то и подстроки мы будем
рассматривать циклические: под подстрокой
, когда
, понимается
substring
. Кроме того, предварительно все индексы берутся по модулю длины строки (в целях упрощения формул я буду опускать явные взятия индексов по модулю).
Рассматриваемый нами Algorithm состоит из Exampleно
фаз. На
-ой фазе (
)
сортируются циклические подстроки длины
. На последней,
-ой фазе, будут сортироваться подстроки
длины
, что эквивалентно сортировке циклических сдвигов.
На каждой фазе Algorithm помимо перестановки
индексов циклических подстрок будет
поддерживать для каждой циклической подстроки, начинающейся в позиции
с длиной
, номер
класса эквивалентности, которому эта substring принадлежит. В самом деле, среди подстрок могут быть одинаковые, и Algorithmу понадобится информация об этом. Кроме того, номера
классов эквивалентности
будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший. Классы будем для удобства нумеровать с нуля. Количество
классов эквивалентности будем хранить в переменной
.
Приведём Example. Рассмотрим строку
. Значения arrayов
и
на каждой стадии с нулевой
по вторую таковы:
Стоит отметить, что в arrayе
возможны неоднозначности. НаExample, на нулевой фазе array мог
равняться: . То, какой именно вариант получится, зависит от конкретной реализации Algorithmа, но
все варианты одинаково правильны. В то же время, в arrayе
никаких неоднозначностей быть не могло. Перейдём теперь к построению Algorithmа. Inputные данные:
char *s; // Inputная string
int n; // длина строки// константы
const int maxlen = ...; // максимальная длина строки
const int alphabet = 256; // размер алфавита, <= maxlen
На нулевой фазе мы должны отсортировать циклические подстроки длины
, т.е. отдельные символы строки,
и разделить их на классы эквивалентности (просто одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать тривиально, наExample, сортировкой подсчётом. Для каждого символа посчитаем, сколько раз он встретился. Потом по этой информации восстановим array
. После
этого, проходом по arrayу
и сравнением символов, строится array
.
int p[maxlen], cnt[maxlen], c[maxlen];memset (cnt, 0, alphabet * sizeof(int));
for (int i=0; i<n; ++i)++cnt[s[i]];
for (int i=1; i<alphabet; ++i)cnt[i] += cnt[i-1];
for (int i=0; i<n; ++i)p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;for (int i=1; i<n; ++i) {if (s[p[i]] != s[p[i-1]]) ++classes;c[p[i]] = classes-1;
}
Далее, пусть мы выполнили
-ю фазу (т.е. вычислили значения arrayов
и
для неё), теперь научимся
за
выполнять следующую,
-ю, фазу. Поскольку фаз всего
, это даст нам
требуемый Algorithm с временем
.
Для этого заметим, что циклическая substring длины
состоит из двух подстрок длины
, которые мы
можем сравнивать между собой за
, используя информацию с предыдущей фазы — номера
классов эквивалентности. Таким образом, для подстроки длины
, начинающейся в позиции
, вся
необходимая информация содержится в паре чисел
(повторимся, мы используем array
с предыдущей фазы). Это даёт нам весьма простое Solution: отсортировать подстроки длины
просто по этим парам чисел,
это и даст нам требуемый порядок, т.е. array
. Однако обычная сортировка, выполняющаяся за время
, нас не устроит — это даст Algorithm построения суффиксного arrayа с временем
(зато этот Algorithm несколько проще в написании, чем описываемый ниже). Как быстро выполнить такую сортировку пар? Поскольку elementы пар не превосходят
, то можно выполнить
сортировку подсчётом. Однако для достижения лучшей скрытой в асимптотике константы вместо сортировки пар придём к сортировке просто чисел. Воспользуемся здесь приёмом, на котором основана так называемая цифровая сортировка: чтобы отсортировать пары, отсортируем их сначала по вторым elementам, а затем — по первым elementам (но уже обязательно стабильной сортировкой, т.е. не нарушающей относительного порядка elementов при равенстве). Однако отдельно вторые elementы уже упорядочены — этот порядок задан в arrayе от предыдущей фазы. Тогда, чтобы упорядочить пары по вторым elementам, надо просто от каждого elementа arrayа
отнять
—
это даст нам порядок сортировки пар по вторым elementам (ведь
даёт упорядочение подстрок длины
, и
при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки). Таким образом, с помощью всего лишь вычитаний от elementов arrayа
мы производим сортировку по
вторым elementам пар. Теперь надо произвести стабильную сортировку по первым elementам пар, её уже
можно выполнить за
с помощью сортировки подсчётом.
Осталось только пересчитать номера
классов эквивалентности, но их уже легко получить, просто пройдя по
полученной новой перестановке
и сравнивая соседние elementы (опять же, сравнивая как пары двух чисел). Приведём реализацию выполнения всех фаз Algorithmа, кроме нулевой. Вводятся дополнительно
временные arrayы
и
(
— содержит перестановку в порядке сортировки по вторым elementам пар,
— новые номера классов эквивалентности).
int pn[maxlen], cn[maxlen];for (int h=0; (1<<h)<n; ++h) {for (int i=0; i<n; ++i) {pn[i] = p[i] - (1<<h);
if (pn[i] < 0) pn[i] += n;}
memset (cnt, 0, classes * sizeof(int));
for (int i=0; i<n; ++i)++cnt[c[pn[i]]];
for (int i=1; i<classes; ++i)cnt[i] += cnt[i-1];
for (int i=n-1; i>=0; --i)p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i=1; i<n; ++i) {int mid1 = (p[i] + (1<<h)) % n, mid2 = (p[i-1] + (1<<h)) % n;if (c[p[i]] != c[p[i-1]] || c[mid1] != c[mid2])++classes;
cn[p[i]] = classes-1;
}
memcpy (c, cn, n * sizeof(int));
}
Этот Algorithm требует
времени и
памяти. Впрочем, если учитывать ещё размер
алфавита,
то Running time становится
, а размер памяти —
.
Applications
Нахождение наименьшего циклического сдвига строки
Вышеописанный Algorithm производит сортировку циклических сдвигов (если к строке не приписывать доллар), а
потому
даст искомую позицию наименьшего циклического сдвига. Running time — .
Поиск подстроки в строке
Пусть it is required в тексте
искать строку
в режиме онлайн (т.е. заранее строку
нужно считать неизвестной).
Построим Suffix array для текста
за
. Теперь подстроку
будем искать следующим
образом: заметим, что искомое вхождение должно быть префиксом какого-либо суффикса
. Поскольку суффиксы у
нас упорядочены (это даёт нам Suffix array), то подстроку
можно искать бинарным поиском по
суффиксам строки. Сравнение текущего суффикса и подстроки
внутри бинарного поиска можно производить
тривиально, за
. Тогда Asymptotic complexity поиска подстроки в тексте становится
.
Сравнение двух подстрок строки
it is required по заданной строке
, произведя некоторый её препроцессинг, научиться за
отвечать на
запросы сравнения двух произвольных подстрок (т.е. проверка, что первая substring равна/меньше/больше второй).
Построим Suffix array за
, при этом сохраним промежуточные результаты: нам
понадобятся arrayы
от каждой фазы. Поэтому памяти поit is required тоже
.
Используя эту информацию, мы можем за
сравнивать любые две подстроки длины, равной степени двойки: для этого достаточно сравнить номера классов эквивалентности из соответствующей фазы. Теперь надо обобщить этот способ на подстроки произвольной длины. Пусть теперь поступил очередной запрос сравнения двух подстрок длины
с началами в индексах
и
. Найдём наибольшую длину блока, помещающегося внутри подстроки такой длины, т.е. наибольшее
такое, что
. Тогда сравнение двух подстрок можно заменить сравнением двух пар перекрывающихся блоков длины
: сначала надо сравнить два блока, начинающихся в позициях
и
, а при равенстве — сравнить два
блока, заканчивающихся в позициях
и
:
Таким образом, Implementation получается Exampleно такой (здесь считается, что вызывающая процедура сама вычисляет , поскольку сделать это за константное время не так легко (по-видимому, быстрее всего — предпосчётом), но в любом случае это не имеет отношения к применению суффиксного arrayа):
int compare (int i, int j, int l, int k) {pair<int,int> a = make_pair (c[k][i], c[k][i+l-(1<<(k-1))]);
pair<int,int> b = make_pair (c[k][j], c[k][j+l-(1<<(k-1))]);
return a == b ? 0 : a < b ? -1 : 1;}
Наибольший общий префикс двух подстрок: способ с
дополнительной памятью
it is required по заданной строке
, произведя некоторый её препроцессинг, научиться за
отвечать на
запросы наибольшего общего префикса (longest common prefix, lcp) для двух произвольных суффиксов с позициями
и
.
Способ, описываемый здесь, требует
дополнительной памяти; другой способ, использующий
линейный объём памяти, но неконстантное время ответа на запрос, описан в следующем разделе.
Построим Suffix array за
, при этом сохраним промежуточные результаты: нам
понадобятся arrayы
от каждой фазы. Поэтому памяти поit is required тоже
.
Пусть теперь поступил очередной запрос: пара индексов
и
. Воспользуемся тем, что мы можем за
сравнивать любые две подстроки длины, являющейся степенью двойки. Для этого будем перебирать степень двойки (от большей к меньшей), и для текущей степени проверять: если подстроки такой длины совпадают, то к ответу прибавить эту степень двойки, а наибольший общий префикс продолжим искать справа от одинаковой части, т.е. к
и
надо прибавить текущую степень двойки. Implementation:
int lcp (int i, int j) {int ans = 0;for (int k=log_n; k>=0; --k)if (c[k][i] == c[k][j]) {ans += 1<<k;
i += 1<<k;
j += 1<<k;
}
return ans;}
Здесь через
обозначена константа, равная логарифму
по основанию 2, округлённому вниз.
Наибольший общий префикс двух подстрок: способ
без дополнительной памяти. Наибольший общий префикс
двух соседних суффиксов
it is required по заданной строке
, произведя некоторый её препроцессинг, научиться отвечать на запросы наибольшего общего префикса (longest common prefix, lcp) для двух произвольных суффиксов с позициями
и
. В отличие от предыдущего метода, описываемый здесь будет выполнять препроцессинг строки за
времени с
памяти. Результатом этого препроцессинга будет являться array (который сам по себе является важным источником информации о строке, и потому использоваться для решения других задач). Ответы же на запрос будут производиться как результат выполнения запроса RMQ (минимум на отрезке, range minimum query) в этом arrayе, поэтому при разных Implementationх можно получить как логарифмическое, так и константное времена работы. Базой для этого Algorithmа является следующая идея: найдём каким-нибудь образом наибольшие общие префиксы для каждой соседней в порядке сортировки пары суффиксов. Иными словами, построим
array
, где
равен наибольшему общему префиксу суффиксов
и
. Этот
array даст нам ответ для любых двух соседних суффиксов строки. Тогда ответ для любых двух суффиксов, не обязательно соседних, можно получить по этому arrayу. В самом деле, пусть поступил запрос с некоторыми
номерами суффиксов
и
. Найдём эти индексы в суффиксном arrayе, т.е. пусть
и
— их позиции в arrayе
(упорядочим их, т.е. пусть
). Тогда ответом на данный запрос будет минимум в arrayе
, взятый
на отрезке
. В самом деле, переход от суффикса
к суффиксу
можно заменить целой
цепочкой переходов, начинающейся с суффикса
и заканчивающейся в суффиксе
, но включающей в себя
все промежуточные суффиксы, находящиеся в порядке сортировки между ними.
Таким образом, если мы имеем такой array
, то ответ на любой запрос наибольшего общего префикса сводится
к запросу минимума на отрезке arrayа
. Эта классическая Task минимума на отрезке (range
minimum query, RMQ) имеет множество решений с различными Asymptotic complexityми, описанные здесь.
Итак, основная наша Task — построение этого arrayа
. Строить его мы будем по ходу Algorithmа
построения суффиксного arrayа: на каждой текущей итерации будем строить array
для циклических
подстрок текущей длины.
После нулевой итерации array
, очевидно, должен быть нулевым.
Пусть теперь мы выполнили
-ю итерацию, получили от неё array
, и должны на текущей
-й
итерации пересчитать этот array, получив новое его значение
. Как мы помним, в Algorithmе
построения суффиксного arrayа циклические подстроки длины
разбивались пополам на две подстроки длины
; воспользуемся этим же приёмом и для построения arrayа
. Итак, пусть на текущей итерации Algorithm вычисления суффиксного arrayа выполнил свою работу, нашёл
новое значение перестановки
подстрок. Будем теперь идти по этому arrayу и смотреть пары соседних подстрок:
и
,
. Разбивая каждую подстроку пополам, мы получаем две различных ситуации:
1) первые половинки подстрок в позициях
и
различаются, и 2) первые половинки совпадают
(напомним, такое сравнение можно легко производить, просто сравнивая номера классов
с предыдущей
итерации). Рассмотрим каждый из этих случаев отдельно. 1) Первые половинки подстрок различались. Заметим, что тогда на предыдущем шаге эти первые половинки необходимо были соседними. В самом деле, классы эквивалентности не могли исчезать (а могут только
появляться), поэтому все различные подстроки длины
дадут (в качестве первых половинок) на текущей
итерации различные подстроки длины
, и в том же порядке. Таким образом, для определения
в этом
случае надо просто взять соответствующее значение из arrayа
. 2) Первые половинки совпадали. Тогда вторые половинки могли как совпадать, так и различаться; при этом, если они различаются, то они совсем не обязательно должны были быть соседними на предыдущей итерации. Поэтому в
этом случае нет простого способа определить
. Для его определения надо поступить так же, как мы и
собираемся потом вычислять наибольший общий префикс для любых двух суффиксов: надо выполнить запрос
минимума (RMQ) на соответствующем отрезке arrayа
. Оценим асимптотику такого Algorithmа. Как мы видели при разборе этих двух случаев, только второй случай даёт увеличение числа классов эквивалентности. Иными словами, можно говорить о том, что каждый новый класс эквивалентности появляется вместе с одним запросом RMQ. Поскольку всего классов эквивалентности может
быть до
, то и искать минимум мы должны за асимптотику
. А для этого надо использовать уже какую-
то структуру данных для минимума на отрезке; эту структуру данных надо будет строить заново на каждой
итерации (которых всего
). Хорошим вариантом структуры данных будет Segment tree: его
можно построить за
, а потом выполнять запросы за
, что как раз и даёт нам итоговую
асимптотику
. Implementation:
int lcp[maxlen], lcpn[maxlen], lpos[maxlen], rpos[maxlen];memset (lcp, 0, sizeof lcp);
for (int h=0; (1<<h)<n; ++h) {for (int i=0; i<n; ++i)rpos[c[p[i]]] = i;
for (int i=n-1; i>=0; --i)lpos[c[p[i]]] = i;
... все действия по построению суфф. arrayа, кроме последней
строки (memcpy) ...
rmq_build (lcp, n-1);
for (int i=0; i<n-1; ++i) {int a = p[i], b = p[i+1];if (c[a] != c[b])lcpn[i] = lcp[rpos[c[a]]];
else {
int aa = (a + (1<<h)) % n, bb = (b + (1<<h)) % n;lcpn[i] = (1<<h) + rmq (lpos[c[aa]], rpos[c[bb]]-1);
lcpn[i] = min (n, lcpn[i]);
} }
memcpy (lcp, lcpn, (n-1) * sizeof(int));
memcpy (c, cn, n * sizeof(int));
}
Здесь помимо arrayа
вводится временный array
с его новым значением. Также поддерживается
array
, который для каждой подстроки хранит её позицию в перестановке
. Функция
—
некоторая функция, строящая структуру данных для минимума по arrayу-первому аргументу, размер его
передаётся вторым аргументом. Функция
returns минимум на отрезке: с первого аргумента по
второй включительно. Из самого Algorithmа построения суффиксного arrayа пришлось только вынести копирование arrayа
, поскольку
во время вычисления
нам понадобятся старые значения этого arrayа. Стоит отметить, что наша Implementation находит длину общего префикса для циклических подстрок, в то время как на практике чаще бывает нужной длина общего префикса для суффиксов в их обычном понимании. В
этом случае надо просто ограничить значения
по окончании работы Algorithmа:
for (int i=0; i<n-1; ++i)lcp[i] = min (lcp[i], min (n-p[i], n-p[i+1]));
Для любых двух суффиксов длину их наибольшего общего префикса теперь можно find как минимум
на соответствующем отрезке arrayа
:
for (int i=0; i<n; ++i)pos[p[i]] = i;
rmq_build (lcp, n-1);
... поступил запрос (i,j) на нахождение LCP ...
int result = rmq (min(i,j), max(i,j)-1);Количество различных подстрок
Выполним препроцессинг, описанный в предыдущем разделе: за
времени и
памяти мы
для каждой пары соседних в порядке сортировки суффиксов найдём длину их наибольшего общего префикса.
Найдём теперь по этой информа
...
C# solution
auto-draft, review before submitusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
char *s; // входная строка
int n; // длина строки
// константы
const int maxlen = ...; // максимальная длина строки
const int alphabet = 256; // размер алфавита, <= maxlen
int p[maxlen], cnt[maxlen], c[maxlen];
memset (cnt, 0, alphabet * sizeof(int));
for (int i=0; i<n; ++i)
++cnt[s[i]];
for (int i=1; i<alphabet; ++i)
cnt[i] += cnt[i-1];
for (int i=0; i<n; ++i)
p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i=1; i<n; ++i) {
if (s[p[i]] != s[p[i-1]]) ++classes;
c[p[i]] = classes-1;
}
int pn[maxlen], cn[maxlen];
for (int h=0; (1<<h)<n; ++h) {
for (int i=0; i<n; ++i) {
pn[i] = p[i] - (1<<h);
if (pn[i] < 0) pn[i] += n;
}
memset (cnt, 0, classes * sizeof(int));
for (int i=0; i<n; ++i)
++cnt[c[pn[i]]];
for (int i=1; i<classes; ++i)
cnt[i] += cnt[i-1];
for (int i=n-1; i>=0; --i)
p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i=1; i<n; ++i) {
int mid1 = (p[i] + (1<<h)) % n, mid2 = (p[i-1] + (1<<h)) % n;
if (c[p[i]] != c[p[i-1]] || c[mid1] != c[mid2])
++classes;
cn[p[i]] = classes-1;
}
memcpy (c, cn, n * sizeof(int));
}
int compare (int i, int j, int l, int k) {
pair<int,int> a = make_pair (c[k][i], c[k][i+l-(1<<(k-1))]);
pair<int,int> b = make_pair (c[k][j], c[k][j+l-(1<<(k-1))]);
return a == b ? 0 : a < b ? -1 : 1;
}
int lcp (int i, int j) {
int ans = 0;
for (int k=log_n; k>=0; --k)
if (c[k][i] == c[k][j]) {
ans += 1<<k;
i += 1<<k;
j += 1<<k;
}
return ans;
}
int lcp[maxlen], lcpn[maxlen], lpos[maxlen], rpos[maxlen];
memset (lcp, 0, sizeof lcp);
for (int h=0; (1<<h)<n; ++h) {
for (int i=0; i<n; ++i)
rpos[c[p[i]]] = i;
for (int i=n-1; i>=0; --i)
lpos[c[p[i]]] = i;
... все действия по построению суфф. массива, кроме последней
строки (memcpy) ...
rmq_build (lcp, n-1);
for (int i=0; i<n-1; ++i) {
int a = p[i], b = p[i+1];
if (c[a] != c[b])
lcpn[i] = lcp[rpos[c[a]]];
else {
int aa = (a + (1<<h)) % n, bb = (b + (1<<h)) % n;
lcpn[i] = (1<<h) + rmq (lpos[c[aa]], rpos[c[bb]]-1);
lcpn[i] = min (n, lcpn[i]);
}
}
memcpy (lcp, lcpn, (n-1) * sizeof(int));
memcpy (c, cn, n * sizeof(int));
}
for (int i=0; i<n-1; ++i)
lcp[i] = min (lcp[i], min (n-p[i], n-p[i+1]));
for (int i=0; i<n; ++i)
pos[p[i]] = i;
rmq_build (lcp, n-1);
... поступил запрос (i,j) на нахождение LCP ...
int result = rmq (min(i,j), max(i,j)-1);
}C++ solution
matched/originalchar *s; // входная строка
int n; // длина строки
// константы
const int maxlen = ...; // максимальная длина строки
const int alphabet = 256; // размер алфавита, <= maxlen
int p[maxlen], cnt[maxlen], c[maxlen];
memset (cnt, 0, alphabet * sizeof(int));
for (int i=0; i<n; ++i)
++cnt[s[i]];
for (int i=1; i<alphabet; ++i)
cnt[i] += cnt[i-1];
for (int i=0; i<n; ++i)
p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i=1; i<n; ++i) {
if (s[p[i]] != s[p[i-1]]) ++classes;
c[p[i]] = classes-1;
}
int pn[maxlen], cn[maxlen];
for (int h=0; (1<<h)<n; ++h) {
for (int i=0; i<n; ++i) {
pn[i] = p[i] - (1<<h);
if (pn[i] < 0) pn[i] += n;
}
memset (cnt, 0, classes * sizeof(int));
for (int i=0; i<n; ++i)
++cnt[c[pn[i]]];
for (int i=1; i<classes; ++i)
cnt[i] += cnt[i-1];
for (int i=n-1; i>=0; --i)
p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i=1; i<n; ++i) {
int mid1 = (p[i] + (1<<h)) % n, mid2 = (p[i-1] + (1<<h)) % n;
if (c[p[i]] != c[p[i-1]] || c[mid1] != c[mid2])
++classes;
cn[p[i]] = classes-1;
}
memcpy (c, cn, n * sizeof(int));
}
int compare (int i, int j, int l, int k) {
pair<int,int> a = make_pair (c[k][i], c[k][i+l-(1<<(k-1))]);
pair<int,int> b = make_pair (c[k][j], c[k][j+l-(1<<(k-1))]);
return a == b ? 0 : a < b ? -1 : 1;
}
int lcp (int i, int j) {
int ans = 0;
for (int k=log_n; k>=0; --k)
if (c[k][i] == c[k][j]) {
ans += 1<<k;
i += 1<<k;
j += 1<<k;
}
return ans;
}
int lcp[maxlen], lcpn[maxlen], lpos[maxlen], rpos[maxlen];
memset (lcp, 0, sizeof lcp);
for (int h=0; (1<<h)<n; ++h) {
for (int i=0; i<n; ++i)
rpos[c[p[i]]] = i;
for (int i=n-1; i>=0; --i)
lpos[c[p[i]]] = i;
... все действия по построению суфф. массива, кроме последней
строки (memcpy) ...
rmq_build (lcp, n-1);
for (int i=0; i<n-1; ++i) {
int a = p[i], b = p[i+1];
if (c[a] != c[b])
lcpn[i] = lcp[rpos[c[a]]];
else {
int aa = (a + (1<<h)) % n, bb = (b + (1<<h)) % n;
lcpn[i] = (1<<h) + rmq (lpos[c[aa]], rpos[c[bb]]-1);
lcpn[i] = min (n, lcpn[i]);
}
}
memcpy (lcp, lcpn, (n-1) * sizeof(int));
memcpy (c, cn, n * sizeof(int));
}
for (int i=0; i<n-1; ++i)
lcp[i] = min (lcp[i], min (n-p[i], n-p[i+1]));
for (int i=0; i<n; ++i)
pos[p[i]] = i;
rmq_build (lcp, n-1);
... поступил запрос (i,j) на нахождение LCP ...
int result = rmq (min(i,j), max(i,j)-1);Java solution
auto-draft, review before submitimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
char *s; // входная строка
int n; // длина строки
// константы
const int maxlen = ...; // максимальная длина строки
const int alphabet = 256; // размер алфавита, <= maxlen
int p[maxlen], cnt[maxlen], c[maxlen];
memset (cnt, 0, alphabet * sizeof(int));
for (int i=0; i<n; ++i)
++cnt[s[i]];
for (int i=1; i<alphabet; ++i)
cnt[i] += cnt[i-1];
for (int i=0; i<n; ++i)
p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i=1; i<n; ++i) {
if (s[p[i]] != s[p[i-1]]) ++classes;
c[p[i]] = classes-1;
}
int pn[maxlen], cn[maxlen];
for (int h=0; (1<<h)<n; ++h) {
for (int i=0; i<n; ++i) {
pn[i] = p[i] - (1<<h);
if (pn[i] < 0) pn[i] += n;
}
memset (cnt, 0, classes * sizeof(int));
for (int i=0; i<n; ++i)
++cnt[c[pn[i]]];
for (int i=1; i<classes; ++i)
cnt[i] += cnt[i-1];
for (int i=n-1; i>=0; --i)
p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i=1; i<n; ++i) {
int mid1 = (p[i] + (1<<h)) % n, mid2 = (p[i-1] + (1<<h)) % n;
if (c[p[i]] != c[p[i-1]] || c[mid1] != c[mid2])
++classes;
cn[p[i]] = classes-1;
}
memcpy (c, cn, n * sizeof(int));
}
int compare (int i, int j, int l, int k) {
pair<int,int> a = make_pair (c[k][i], c[k][i+l-(1<<(k-1))]);
pair<int,int> b = make_pair (c[k][j], c[k][j+l-(1<<(k-1))]);
return a == b ? 0 : a < b ? -1 : 1;
}
int lcp (int i, int j) {
int ans = 0;
for (int k=log_n; k>=0; --k)
if (c[k][i] == c[k][j]) {
ans += 1<<k;
i += 1<<k;
j += 1<<k;
}
return ans;
}
int lcp[maxlen], lcpn[maxlen], lpos[maxlen], rpos[maxlen];
memset (lcp, 0, sizeof lcp);
for (int h=0; (1<<h)<n; ++h) {
for (int i=0; i<n; ++i)
rpos[c[p[i]]] = i;
for (int i=n-1; i>=0; --i)
lpos[c[p[i]]] = i;
... все действия по построению суфф. массива, кроме последней
строки (memcpy) ...
rmq_build (lcp, n-1);
for (int i=0; i<n-1; ++i) {
int a = p[i], b = p[i+1];
if (c[a] != c[b])
lcpn[i] = lcp[rpos[c[a]]];
else {
int aa = (a + (1<<h)) % n, bb = (b + (1<<h)) % n;
lcpn[i] = (1<<h) + rmq (lpos[c[aa]], rpos[c[bb]]-1);
lcpn[i] = min (n, lcpn[i]);
}
}
memcpy (lcp, lcpn, (n-1) * sizeof(int));
memcpy (c, cn, n * sizeof(int));
}
for (int i=0; i<n-1; ++i)
lcp[i] = min (lcp[i], min (n-p[i], n-p[i+1]));
for (int i=0; i<n; ++i)
pos[p[i]] = i;
rmq_build (lcp, n-1);
... поступил запрос (i,j) на нахождение LCP ...
int result = rmq (min(i,j), max(i,j)-1);
}Материал разбит как Algorithmическая Task: изучить постановку, понять асимптотику и реализовать Algorithm на выбранном языке.
Vacancies for this task
Active vacancies with overlapping task tags are shown.