e-maxx_algo
.pdfАлгоритм Рабина-Карпа поиска подстроки в строке за O (N)
Этот алгоритм базируется на хэшировании строк, и тех, кто не знаком с темой, отсылаю к "Алгоритмам хэширования в задачах на строки".
Авторы алгоритма - Рабин (Rabin) и Карп (Karp), 1987 год.
Дана строка S и текст T, состоящие из маленьких латинских букв. Требуется найти все вхождения строки S в текст T
за время O (|S| + |T|).
Алгоритм. Посчитаем хэш для строки S. Посчитаем значения хэшей для всех префиксов строки T. Теперь переберём все подстроки T длины |S| и каждую сравним с |S| за время O (1).
Реализация
string s, t; // входные данные
//считаем все степени p const int p = 31;
vector<long long> p_pow (max (s.length(), t.length())); p_pow[0] = 1;
for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p;
//считаем хэши от всех префиксов строки T
vector<long long> h (t.length()); for (size_t i=0; i<t.length(); ++i)
{
h[i] = (t[i] - 'a' + 1) * p_pow[i]; if (i) h[i] += h[i-1];
}
//считаем хэш от строки S long long h_s = 0;
for (size_t i=0; i<s.length(); ++i)
h_s += (s[i] - 'a' + 1) * p_pow[i];
//перебираем все подстроки T длины |S| и сравниваем их for (size_t i = 0; i + s.length() - 1 < t.length(); ++i)
{
long long cur_h = h[i+s.length()-1]; if (i) cur_h -= h[i-1];
// приводим хэши к одной степени и сравниваем if (cur_h == h_s * p_pow[i])
cout << i << ' ';
}
Разбор выражений. Обратная польская нотация
Дана строка, представляющая собой математическое выражение, содержащее числа, переменные, различные операции. Требуется вычислить его значение за , где — длина строки.
Здесь описан алгоритм, который переводит это выражение в так называемую обратную польскую нотацию (явным или неявным образом), и уже в ней вычисляет выражение.
Обратная польская нотация
Обратная польская нотация — это форма записи математических выражений, в которой операторы расположены после своих операндов.
Например, следующее выражение:
в обратной польской нотации записывается следующим образом:
Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 г. польским математиком Яном Лукасевичем.
Удобство обратной польской нотации заключается в том, что выражения, представленные в такой форме, очень легко вычислять, причём за линейное время. Заведём стек, изначально он пуст. Будем двигаться слева направо по выражению в обратной польской нотации; если текущий элемент — число или переменная, то кладём на вершину стека её значение; если же текущий элемент — операция, то достаём из стека два верхних элемента (или один, если операция унарная), применяем к ним операцию, и результат кладём обратно в стек. В конце концов в стеке останется ровно один элемент - значение выражения.
Очевидно, этот простой алгоритм выполняется за , т.е. порядка длины выражения.
Разбор простейших выражений
Пока мы рассматриваем только простейший случай: все операции бинарны (т.е. от двух аргументов), и все левоассоциативны (т.е. при равенстве приоритетов выполняются слева направо). Скобки разрешены.
Заведём два стека: один для чисел, другой для операций и скобок (т.е. стек символов). Изначально оба стека пусты. Для второго стека будем поддерживать предусловие, что все операции упорядочены в нём по строгому убыванию приоритета, если двигаться от вершины стека. Если в стеке есть открывающие скобки, то упорядочен каждый блок операций, находящийся между скобками, а весь стек в таком случае не обязательно упорядочен.
Будем идти по строке слева направо. Если текущий элемент — цифра или переменная, то положим в стек значение этого числа/переменной. Если текущий элемент — открывающая скобка, то положим её в стек. Если текущий элемент
— закрывающая скобка, то будем выталкивать из стека и выполнять все операции до тех пор, пока мы не извлечём открывающую скобку (т.е., иначе говоря, встречая закрывающую скобку, мы выполняем все операции, находящиеся внутри этой скобки). Наконец, если текущий элемент — операция, то, пока на вершине стека находится операция с таким же или большим приоритетом, будем выталкивать и выполнять её.
После того, как мы обработаем всю строку, в стеке операций ещё могут остаться некоторые операции, которые ещё не были вычислены, и нужно выполнить их все (т.е. действуем аналогично случаю, когда встречаем закрывающую скобку).
Вот реализация данного метода на примере обычных операций :
bool delim (char c) { return c == ' ';
}
bool is_op (char c) {
return c=='+' || c=='-' || c=='*' || c=='/' || c=='%';
}
int priority (char op) { return
op == '+' || op == '-' ? 1 :
op == '*' || op == '/' || op == '%' ? 2 : -1;
} |
|
|
|
|
void process_op (vector<int> & st, char op) { |
|
|
||
int r = st.back(); |
st.pop_back(); |
|
|
|
int l = st.back(); |
st.pop_back(); |
|
|
|
switch (op) { |
st.push_back (l + r); |
break; |
|
|
case '+': |
|
|||
case '-': |
st.push_back (l - r); |
break; |
|
|
case '*': |
st.push_back (l * r); |
break; |
|
|
case '/': |
st.push_back (l / r); |
break; |
|
|
case '%': |
st.push_back (l % r); |
break; |
|
|
} |
|
|
|
|
} |
|
|
|
|
int calc (string & s) { |
|
|
|
|
vector<int> st; |
|
|
|
|
vector<char> op; |
|
|
|
|
for (size_t i=0; i<s.length(); ++i) |
|
|
||
if (!delim (s[i])) |
|
|
||
if (s[i] == '(') |
|
|
||
|
op.push_back ('('); |
|
||
else if (s[i] == ')') { |
|
|
||
|
while (op.back() != '(') |
op. |
||
pop_back(); |
process_op (st, op.back()), |
|||
op.pop_back(); |
|
|
||
} |
|
|
||
|
|
|
||
else if (is_op (s[i])) { |
|
|
||
|
char curop = s[i]; |
|
|
|
>= priority(s[i])) |
while (!op.empty() && priority(op.back()) |
|||
process_op (st, op.back()), |
op. |
|||
pop_back(); |
||||
|
|
|
op.push_back (curop);
}
else {
string operand;
while (s[i] >= 'a' && s[i] <= 'z' || isdigit
(s[i]))
operand += s[i++];
--i;
if (isdigit (operand[0]))
st.push_back (atoi (operand.c_str()));
else
st.push_back
(get_variable_val (operand));
}
while (!op.empty())
process_op (st, op.back()), op.pop_back(); return st.back();
}
Таким образом, мы научились вычислять значение выражения за |
, и при этом мы неявно воспользовались |
обратной польской нотацией: мы расположили операции в таком порядке, когда к моменту вычисления очередной операции оба её операнда уже вычислены. Слегка модифицировав вышеописанный алгоритм, можно получить выражение в обратной польской нотаци и в явном виде.
Унарные операции
Теперь предположим, что выражение содержит унарные операции (т.е. от одного аргумента). Например, особенно часто встречаются унарный плюс и минус.
Одно из отличий этого случая заключается в необходимости определения того, является ли текущая операция унарной или бинарной.
Можно заметить, что перед унарной операцией всегда стоит либо другая операция, либо открывающая скобка,
либо вообще ничего (если она стоит в самом начале строки). Перед бинарной операцией, напротив, всегда стоит
либо операнд (число/переменная), либо закрывающая скобка. Таким образом, достаточно завести какой-нибудь флаг для указания того, может ли следующая операция быть унарной или нет.
Ещё чисто реализационная тонкость — как различать унарные и бинарные операции при извлечении из стека и вычислении. Здесь можно, например, для унарных операций вместо символа класть в стек .
Приоритет для унарных операций нужно выбирать таким, чтобы он был больше приоритетов всех бинарных операций.
Кроме того, надо заметить, что унарные операции фактически являются правоассоциативными — если подряд идут несколько унарных операций, то они должны обрабатываться справа налево (для описания этого случая см. ниже; приведённый здесь код уже учитывает правоассоциативность).
Реализация для бинарных операций и унарных операций :
bool delim (char c) { return c == ' ';
}
bool is_op (char c) {
return c=='+' || c=='-' || c=='*' || c=='/' || c=='%';
}
int priority (char op) { if (op < 0)
return op == -'+' || op == '-' ? 4;
return
op == '+' || op == '-' ? 1 :
op == '*' || op == '/' || op == '%' ? 2 : -1;
}
void process_op (vector<int> & st, char op) { if (op < 0) {
int l = st.back(); st.pop_back(); switch (-op) {
case '+': st.push_back (l); break; case '-': st.push_back (-l); break;
}
}
else {
int r = st.back(); st.pop_back(); int l = st.back(); st.pop_back(); switch (op) {
case '+': st.push_back (l + r); break; case '-': st.push_back (l - r); break; case '*': st.push_back (l * r); break; case '/': st.push_back (l / r); break; case '%': st.push_back (l % r); break;
}
}
}
int calc (string & s) {
bool may_unary = true; vector<int> st; vector<char> op;
for (size_t i=0; i<s.length(); ++i) if (!delim (s[i]))
if (s[i] == '(') {
op.push_back ('('); may_unary = true;
}
else if (s[i] == ')') {
while (op.back() != '(')
process_op (st, op.back()), op.
pop_back();
op.pop_back(); may_unary = false;
}
else if (is_op (s[i])) { char curop = s[i];
if (may_unary && isunary (curop)) curop =
-curop;
while (!op.empty() && (
curop >= 0 && priority(op.back())
>= priority(curop)
|| curop < 0 && priority(op.back())
> priority(curop))
)
process_op (st, op.back()), op.
pop_back();
op.push_back (curop); may_unary = true;
}
else {
string operand;
while (s[i] >= 'a' && s[i] <= 'z' || isdigit
(s[i]))
operand += s[i++];
--i;
st.push_back (get_val (operand)); may_unary = false;
}
while (!op.empty())
process_op (st, op.back()), op.pop_back(); return st.back();
}
Стоит заметить, что в простейших случаях, например, когда из унарных операций разрешены только и , правоассоциативность не играет никакой роли, поэтому в таких ситуациях никаких усложнений в схему можно
не вводить. Т.е. цикл:
while (!op.empty() |
&& ( |
|
curop >= 0 |
&& priority(op.back()) |
|
>= priority(curop) |
0 && priority(op.back()) |
|
|| curop < |
||
> priority(curop)) |
|
|
) |
(st, op.back()), |
op. |
process_op |
||
pop_back(); |
|
|
Можно заменить на: |
|
|
|
|
|
while (!op.empty() |
&& priority(op.back()) |
|
>= priority(curop)) |
(st, op.back()), |
op. |
process_op |
||
pop_back(); |
|
|
Правоассоциативность
Правоассоциативность оператора означает, что при равенстве приоритетов операторы вычисляются справа налево (соотвественно, левоассоциативность - когда слева направо).
Как уже было отмечено выше, унарные операторы обычно являются правоассоциативными. Другой пример -
обычно операция возведения в степень считается правоассоциативной (действительно, a^b^c обычно воспринимается как a^(b^c), а не (a^b)^c).
Какие отличия нужно внести в алгоритм, чтобы корректно обрабатывать правоассоциативность? На самом деле, изменения нужны самые минимальные. Единственное отличие будет проявляться только при
равенстве приоритетов, и заключается оно в том, что операции с равным приоритетом, находящиеся на вершине стека, не должны выполнять раньше текущей операции.
Таким образом, единственные отличия нужно внести в функцию calc:
int calc (string & s) {
...
while (!op.empty() && ( left_assoc(curop) && priority(op.
back()) >= priority(curop)
|| !left_assoc(curop) && priority
(op.back()) > priority(curop)))
...
}
Суффиксный массив
Дана строка |
длины . |
|
|
-ым суффиксом строки называется подстрока |
, |
. |
|
Тогда суффиксным массивом строки называется перестановка индексов суффиксов |
|||
, |
, которая задаёт порядок суффиксов в порядке лексикографической |
||
сортировки. Иными словами, нужно выполнить сортировку всех суффиксов заданной строки. |
|||
Например, для строки |
суффиксный массив будет равен: |
|
|
|
|
|
|
|
|
|
|
Построение за
Строго говоря, описываемый ниже алгоритм будет выполнять сортировку не суффиксов, а циклических сдвигов строки. Однако из этого алгоритма легко получить и алгоритм сортировки суффиксов: достаточно приписать в конец строки произвольный символ, который заведомо меньше любого символа, из которого может состоять
строка (например, это может быть доллар или шарп; в языке C в этих целях можно использовать уже имеющийся нулевой символ).
Сразу заметим, что поскольку мы сортируем циклические сдвиги, то и подстроки мы будем
рассматривать циклические: под подстрокой |
, когда |
, понимается |
|
подстрока |
. Кроме того, предварительно все индексы берутся по модулю длины строки |
(в целях упрощения формул я буду опускать явные взятия индексов по модулю).
Рассматриваемый нами алгоритм состоит из примерно |
фаз. На -ой фазе ( |
) |
|
сортируются циклические подстроки длины . На последней, |
-ой фазе, будут сортироваться подстроки |
||
длины |
, что эквивалентно сортировке циклических сдвигов. |
|
|
На каждой фазе алгоритм помимо перестановки |
индексов циклических подстрок будет |
||
поддерживать для каждой циклической подстроки, начинающейся в позиции с длиной |
, номер |
класса эквивалентности, которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера классов эквивалентности
будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший. Классы будем для удобства нумеровать с нуля. Количество классов эквивалентности будем хранить в переменной .
Приведём пример. Рассмотрим строку |
. Значения массивов |
и |
на каждой стадии с нулевой |
по вторую таковы: |
|
|
|
|
|
|
|
|
|
|
|
Стоит отметить, что в массиве |
возможны неоднозначности. Например, на нулевой фазе массив мог |
равняться: |
. То, какой именно вариант получится, зависит от конкретной реализации алгоритма, но |
все варианты одинаково правильны. В то же время, в массиве никаких неоднозначностей быть не могло. Перейдём теперь к построению алгоритма. Входные данные:
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) { |
|
++classes; |
|
|
||
|
if (s[p[i]] != s[p[i-1]]) |
|
|
|||
} |
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) { |
|
mid2 = (p[i-1] + (1<<h)) % n; |
|
int mid1 = (p[i] + (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; |
} |
|
Наибольший общий префикс двух подстрок: способ с дополнительной памятью
Требуется по заданной строке , произведя некоторый её препроцессинг, научиться за |
отвечать на |
запросы наибольшего общего префикса (longest common prefix, lcp) для двух произвольных суффиксов с позициями и .
Способ, описываемый здесь, требует |
дополнительной памяти; другой способ, использующий |
линейный объём памяти, но неконстантное время ответа на запрос, описан в следующем разделе.
Построим суффиксный массив за |
, при этом сохраним промежуточные результаты: нам |
понадобятся массивы от каждой фазы. Поэтому памяти потребуется тоже .
Пусть теперь поступил очередной запрос: пара индексов и . Воспользуемся тем, что мы можем за
сравнивать любые две подстроки длины, являющейся степенью двойки. Для этого будем перебирать степень двойки (от большей к меньшей), и для текущей степени проверять: если подстроки такой длины совпадают, то к ответу прибавить эту степень двойки, а наибольший общий префикс продолжим искать справа от одинаковой части, т.е. к и надо прибавить текущую степень двойки.
Реализация:
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, округлённому вниз.
Наибольший общий префикс двух подстрок: способ без дополнительной памяти. Наибольший общий префикс двух соседних суффиксов
Требуется по заданной строке , произведя некоторый её препроцессинг, научиться отвечать на запросы наибольшего общего префикса (longest common prefix, lcp) для двух произвольных суффиксов с позициями и .
В отличие от предыдущего метода, описываемый здесь будет выполнять препроцессинг строки за
времени с |
памяти. Результатом этого препроцессинга будет являться массив (который сам по себе |
является важным источником информации о строке, и потому использоваться для решения других задач). Ответы же на запрос будут производиться как результат выполнения запроса RMQ (минимум на отрезке, range minimum query) в
этом массиве, поэтому при разных реализациях можно получить как логарифмическое, так и константное времена работы.
Базой для этого алгоритма является следующая идея: найдём каким-нибудь образом наибольшие общие префиксы для каждой соседней в порядке сортировки пары суффиксов. Иными словами, построим массив , где равен наибольшему общему префиксу суффиксов и . Этот
массив даст нам ответ для любых двух соседних суффиксов строки. Тогда ответ для любых двух суффиксов, не обязательно соседних, можно получить по этому массиву. В самом деле, пусть поступил запрос с некоторыми
номерами суффиксов и |
. Найдём эти индексы в суффиксном массиве, т.е. пусть |
и |
— их позиции в массиве |
||||||
(упорядочим их, т.е. пусть |
). Тогда ответом на данный запрос будет минимум в массиве |
, взятый |
|||||||
на отрезке |
. В самом деле, переход от суффикса |
к суффиксу |
можно заменить целой |
|
|||||
цепочкой переходов, начинающейся с суффикса |
и заканчивающейся в суффиксе |
, но включающей в себя |
|||||||
все промежуточные суффиксы, находящиеся в порядке сортировки между ними. |
|
|
|
||||||
Таким образом, если мы имеем такой массив |
, то ответ на любой запрос наибольшего общего префикса сводится |
||||||||
к запросу минимума на отрезке массива |
. Эта классическая задача минимума на отрезке (range |
||||||||
minimum query, RMQ) имеет множество решений с различными асимптотиками, описанные здесь. |
|
||||||||
Итак, основная наша задача — построение этого массива |
. Строить его мы будем по ходу алгоритма |
||||||||
построения суффиксного массива: на каждой текущей итерации будем строить массив |
для циклических |
||||||||
подстрок текущей длины. |
|
|
|
|
|
|
|
|
|
После нулевой итерации массив |
, очевидно, должен быть нулевым. |
|
|
|
|
||||
Пусть теперь мы выполнили |
-ю итерацию, получили от неё массив |
, и должны на текущей |
-й |
||||||
итерации пересчитать этот массив, получив новое его значение |
. Как мы помним, в алгоритме |
|