Алгоритмы 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) {

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;

}

Наибольший общий префикс двух подстрок: способ с дополнительной памятью

запросы наибольшего общего префикса (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) имеет множество решений с различными асимптотиками, описанные здесь.

и, . Разбивая каждую подстроку пополам, мы получаем две различных ситуации:

1) Первые половинки подстрок различались. Заметим, что тогда на предыдущем шаге эти первые половинки

2) Первые половинки совпадали. Тогда вторые половинки могли как совпадать, так и различаться; при этом, если они различаются, то они совсем не обязательно должны были быть соседними на предыдущей итерации. Поэтому в этом случае нет простого способа определить . Для его определения надо поступить так же, как мы и

собираемся потом вычислять наибольший общий префикс для любых двух суффиксов: надо выполнить запрос минимума (RMQ) на соответствующем отрезке массива .

Оценим асимптотику такого алгоритма. Как мы видели при разборе этих двух случаев, только второй случай даёт увеличение числа классов эквивалентности. Иными словами, можно говорить о том, что каждый новый

класс эквивалентности появляется вместе с одним запросом RMQ. Поскольку всего классов эквивалентности может

то структуру данных для минимума на отрезке; эту структуру данных надо будет строить заново на каждой

Реализация:

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[p[i]] = i;

for (int i=n-1; i>=0; --i) lpos[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));

}

некоторая функция, строящая структуру данных для минимума по массиву-первому аргументу, размер его передаётся вторым аргументом. Функция возвращает минимум на отрезке: с первого аргумента по второй включительно.