e-maxx_algo

if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts; tp=r[tv]-(tp-r[ts-2])+2; goto suff;

}

}

void build() { fill(r,r+N,INF); s[0]=1; l[0]=-1; r[0]=-1; l[1]=-1; r[1]=-1;

memset (t, -1, sizeof t); fill(t[1],t[1]+26,0);

for (int i=0; i<a.size(); ++i) ukkadd (a[i]-'a');

}

Тот же самый код, прокомментированный:

if (r[tv]<tp) { // проверим, не вылезли ли мы за пределы текущего ребра

//если вылезли, найдем следующее ребро. Если его нет

-создадим лист и прицепим к дереву

if (t[tv][c]==-1) {t[tv][c]=ts;l[ts]=la-1;p[ts++]=tv;tv=s [tv];tp=r[tv]+1;goto suff;}

tv=t[tv][c];tp=l[tv]; // в противном случае просто перейдем к следующему ребру

}

if (tp==-1 || c==a[tp]) tp++; else { // если буква на ребре совпадает

сc то идем по ребру, а иначе

//разделяем ребро на два. Посередине - вершина ts l[ts]=l[tv];r[ts]=tp-1;p[ts]=p[tv];t[ts][a[tp]]=tv;

//ставим лист ts+1. Он соответствует переходу по c. t[ts][c]=ts+1;l[ts+1]=la-1;p[ts+1]=ts;

//обновляем параметры текущей вершины. Не забыть про

переход от предка tv к ts. l[tv]=tp;p[tv]=ts;t[p[ts]][a[l[ts]]]=ts;ts+=2;

// готовимся к спуску: поднялись на ребро и перешли по суффиксной ссылке.

//tp будет отмечать, где мы в текущем суффиксе. tv=s[p[ts-2]];tp=l[ts-2];

//пока текущий суффикс не кончился, топаем вниз

while (tp<=r[ts-2]) {tv=t[tv][a[tp]];tp+=r[tv]-l[tv]+1;}

tp=r[tv]-(tp-r[ts-2])+2;goto suff;

}

}

void build() { fill(r,r+N,INF);

//инициализируем данные для корня дерева s[0]=1;

l[0]=-1; r[0]=-1; l[1]=-1; r[1]=-1;

memset (t, -1, sizeof t); fill(t[1],t[1]+26,0);

//добавляем текст в дерево по одной букве for (int i=0; i<a.size(); ++i)

ukkadd (a[i]-'a');

}

Задачи в online judges

Задачи, которые можно решить, используя суффиксное дерево:

● UVA #10679 "I Love Strings!!!" [сложность: средняя] char,int> next;

node (int l=0, int r=0, int par=-1) : l(l), r(r), par(par), link(-1) {} int len() { return r - l; } int

Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца

Дана строка длины .

Тандемным повтором (tandem repeat) в ней называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов такими, что подстрока — это

две одинаковые строки, записанные подряд.

Задача заключается в том, чтобы найти все тандемные повторы. Упрощённые варианты этой задачи: найти любой тандемный повтор или найти длиннейший тандемный повтор.

Примечание. Во избежание путаницы все строки в статье мы будем считать 0-индексированными, т.е. первый символ строки имеет индекс 0.

Описываемый здесь алгоритм был опубликован в 1982 г. Мейном и Лоренцем (см. список литературы).

Пример

Рассмотрим тандемные повторы на примере какой-нибудь простой строки, например:

В этой строке присутствуют следующие тандемные повторы:

●

●

●

Другой пример:

Здесь есть только два тандемных повтора:

●

●

Число тандемных повторов

с коротким периодом будет содержать очень много тандемных повторов

Сдругой стороны, сам по себе этот факт никак не препятствует существованию алгоритма с асимптотикой

,поскольку алгоритм может выдавать тандемные повторы в том или ином сжатом виде, группами

по несколько штук сразу.

Более того, существует понятие серий — четвёрок чисел, которые описывают целую группу периодических подстрок. Было доказано, что число серий в любой строке линейно по отношению к длине строки.

Впрочем, описываемый ниже алгоритм не использует понятие серий, поэтому не будем детализировать это понятие. Приведём здесь и другие интересные результаты, относящиеся к количеству тандемных повторов:

●Известно, что если рассматривать только примитивные тандемные повторы (т.е. такие, половинки которых не являются кратными строками), то их количество в любой строке — .

выходе алгоритма Крочемора нахождения всех тандемных повторов.) ● Строки Фибоначчи, определяемые следующим образом:

являются "сильно" периодичными.

Число тандемных повторов в -ой строке Фибоначчи длины , даже сжатых с помощью троек Крочемора, составляет .

Число примитивных тандемных повторов в строках Фибоначчи — также имеет порядок .

Алгоритм Мейна-Лоренца

Идея алгоритма Мейна-Лоренца довольно стандартна: это алгоритм "разделяй-и-властвуй".

Кратко он заключается в том, что исходная строка разбивается пополам, решение запускается от каждой из двух половинок по отдельности (тем самым мы найдём все тандемные повторы, располагающиеся только в первой или только во второй половинке). Дальше идёт самая сложная часть — это нахождение тандемных повторов, начинающихся в первой половине и заканчивающихся во второй (назовём такие тандемные повторы

для удобства пересекающими). Как именно это делается — и есть сама суть алгоритма Мейна-Лоренца; это мы подробно опишем ниже.

Асимптотика алгоритма "разделяй-и-властвуй" хорошо исследована. В частности, для нас важно, что если мы

Поиск пересекающих тандемных повторов

Итак, алгоритм Мейна-Лоренца свёлся к тому, чтобы по заданной строке научиться искать все пересекающие тандемные повторы, т.е. такие, которые начинаются в первой половине строки, а заканчиваются — во второй.

Обозначим через и две половинки строки :

(их длины примерно равны длине строки , делённой пополам).

Правые и левые тандемные повторы

Рассмотрим произвольный тандемный повтор и посмотрим на его средний символ (точнее, на тот символ, с которого начинается вторая половинка тандема; т.е. если тандемный повтор — это подстрока , то

средним символом будет .

Тогда назовём тандемный повтор левым или правым в зависимости от того, где находится этот символ —

встроке или в строке . (Можно сказать и так: тандемный повтор называется левым, если большая его часть лежит

влевой половине строки ; иначе — тандемный повтор называется правым.)

Научимся искать все левые тандемные повторы; для правых всё будет аналогично.

Искать все тандемные повторы мы будем, перебирая эту позицию : т.е.

найдём сначала все тандемные повторы с одним значением , затем с другим значением, и т.д. — перебирая все возможные значения от до .

Например, рассмотрим такую строку:

тандемного повтора, попавшим в половинку .

Критерий наличия тандемного повтора с заданным центром

Итак, мы должны научиться для зафиксированного значения быстро искать все тандемные повторы, соответствующие ему.

Чтобы искать правые тандемные повторы, надо действовать аналогично: мы определяем центр как

символ, соответствующий последнему символу тандемного повтора, попавшему в первую строку.

Асимптотика

с всевозможными длинами кусочков и , удовлетворяющими условиям:

Реализация

повторы данной строки в сжатом виде (в виде групп, описываемых четвёрками чисел).

отдельности. Этот вывод при решении реальных задач легко будет заменить на какие-то другие, более эффективные, действия, например, на поиск наидлиннейшего тандемного повтора или подсчёт количества тандемных повторов.

vector<int> z_function (const string & s) { int n = (int) s.length(); vector<int> z (n);

for (int i=1, l=0, r=0; i<n; ++i) { if (i <= r)

z[i] = min (r-i+1, z[i-l]);

while (i+z[i] < n && s[z[i]] == s[i+z[i]]) ++z[i];

if (i+z[i]-1 > r)

l = i, r = i+z[i]-1;

}

return z;

}

void output_tandem (const string & s, int shift, bool left, int cntr, int l, int l1, int l2) {

int pos; if (left)

pos = cntr-l1;

else

pos = cntr-l1-l2-l1+1;

cout << "[" << shift + pos << ".." << shift + pos+2*l-1 << "] = " << s.substr (pos, 2*l) << endl;

}

void output_tandems (const string & s, int shift, bool left, int cntr, int l, int k1, int k2) {

for (int l1=1; l1<=l; ++l1) {

if (left && l1 == l) break; if (l1 <= k1 && l-l1 <= k2)

output_tandem (s, shift, left, cntr, l, l1, l-l1);

}

}

inline int get_z (const vector<int> & z, int i) { return 0<=i && i<(int)z.size() ? z[i] : 0;

}

void find_tandems (string s, int shift = 0) { int n = (int) s.length();

if (n == 1) return;

int nu = n/2, nv = n-nu; string u = s.substr (0, nu),

v = s.substr (nu);

string ru = string (u.rbegin(), u.rend()), rv = string (v.rbegin(), v.rend());

find_tandems (u, shift); find_tandems (v, shift + nu);

vector<int> z1 = z_function (ru),

z2 = z_function (v + '#' + u), z3 = z_function (ru + '#' + rv), z4 = z_function (v);

for (int cntr=0; cntr<n; ++cntr) { int l, k1, k2;

if (cntr < nu) {

l = nu - cntr;

k1 = get_z (z1, nu-cntr); k2 = get_z (z2, nv+1+cntr);

}

else {

l = cntr - nu + 1;

k1 = get_z (z3, nu+1 + nv-1-(cntr-nu)); k2 = get_z (z4, (cntr-nu)+1);

}

if (k1 + k2 >= l)

output_tandems (s, shift, cntr<nu, cntr, l, k1, k2);

}

}

Литература

●Michael Main, Richard J. Lorentz. An O (n log n) Algorithm for Finding All Repetitions in a String [1982]

●Bill Smyth. Computing Patterns in Strings [2003]

●Билл Смит. Методы и алгоритмы вычислений на строках [2006]

Поиск подстроки в строке с помощью Z- или Префикс-функции

Даны строки S и T. Требуется найти все вхождения строки S в текст T за O (N), где N - суммарная длина строк S и T.

Алгоритм

Образуем строку S$T, где $ - некий разделитель, который не встречается ни в S, ни в T.

Вычислим для полученной строки префикс-функцию P за O (N). Пройдёмся по массиву P, и рассмотрим все его элементы, которые равны |S| (длине S). По определению префикс-фунции, это означает, что в это месте оканчивается подстрока, совпадающая с |S|, т.е. искомое вхождение. Таким образом, мы нашли все вхождения. Этот алгоритм называется алгоритмом КМП (Кнута-Морриса-Пратта).

Теперь решим эту же задачу с помощью Z-функции. Построим за O (N) массив Z - Z-функцию строки S$T. Пройдёмся по всем его элементам, и рассмотрим те из них, которые равны |S|. По определению, в этом месте начинается подстрока, совпадающая с S. Таким образом, мы нашли все вхождения.

Решение задачи "сжатие строки" за O (N)

Дана строка S. Требуется найти такую строку T, что строка S получается многократным повторением T. Из всех возможных T нужно выбрать наименьшую по длине.

Эту задачу очень просто решить за O (N) с помощью префикс-функции.

Итак, пусть массив P - префикс-функция строки S, которую можно вычислить за O (N).

Теперь рассмотрим значение последнего элемента P: P[N-1]. Если N делится на (N - P[N-1]), то ответ существует, и это N - P[N-1] первых букв строки S. Если же не делится, то ответа не существует.

Корректность этого метода легко понять. P[N-1] равно длине наидлиннейшего собственного суффикса строки

S, совпадающего с префиксом S. Если ответ существует, то, очевидно, начальный кусок строки S длиной (N - P[N-1]) и будет ответом, и, следовательно, N будет делиться на (N - P[N-1]). Если же ответа не существует, то (N - P[N-1]) будет равно какому-то непонятному значению, на которое N делиться не будет (иначе бы ответ существовал).

Реализация

int n = (int) s.length(); vector<int> p (n);

// ... здесь вычисление префикс-функции ...

int l = n - p[n-1]; if (n % l == 0)

cout << s.substr (l);

else

cout << "No Solution";