Алгоритмы C++

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

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

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);

Количество различных подстрок

Выполним препроцессинг, описанный в предыдущем разделе: за времени и памяти мы

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

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

д. Фактически, мы берём очередной в порядке сортировки суффикс и смотрим, какие его префиксы дают новые подстроки. Тем самым мы, очевидно, не упустим из виду никакие из подстрок.

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

Суффиксный автомат

Формальное определение. Суффиксным автоматом (suffix automaton) строки S называется

минимальный детерминированный автомат, который распознаёт все суффиксы строки S, и только их. (суффиксами также считаются вся строка, а также пустая строка). В англоязычной литературе суффиксный автомат называется suffix automaton (во множественном числе automata), а также DAWG (directed acyclic word graph).

Расшифруем это определение. Суффиксный автомат M имеет некоторое конечное множество состояний, среди которых выделено начальное состояние Init, а также для всех состояний указано, являются ли они терминальными. Между некоторыми состояниями установлены переходы по символам из заданного алфавита (то, что автомат детерминированный, означает, что из каждого состояния по каждому символу есть не более одного перехода): если мы находимся в некотором состоянии и на вход поступает какой-то символ, то мы переходим по соответствующему переходу (т.е. по этому самому символу) в новое состояние. Говорят, что автомат

"распознаёт строку", если, стартуя из начального состояния Init, выполнив последовательно переходы по символам этой строки, мы придём в терминальное состояние (если в какой-то момент мы попытались пройти по несуществующему переходу, то мы останавливаемся, и автомат такую строку не распознаёт).

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

Условимся говорить, что некоторой строке T соответствует состояние p, если, стартовав в состоянии Init и выполнив все переходы по символам этой строки T, мы придём в состояние p. Например, можно говорить, что

любому суффиксу строки S (по которой построен автомат) соответствует терминальное состояние, а любой другой строке - соответствует нетерминальное состояние, или вовсе никакое состояние не соответствует (если в какой-то момент мы попытались совершить несуществующий переход).

Итак, пусть дана строка S длины N в некотором алфавите размера K. Требуется построить суффиксный автомат для неё.

Примеры

Для развития интуиции приведём несколько примеров суффиксных автоматов.

Состояния будем обозначать числами (за исключением начального состояния Init), терминальные состояния - отмечать звёздочками, переходы - стрелочками с подписанными поверх них буквами.

S = ""

Init*

S = "a"	-a-	1*
Init*
S = "aa"		1*	-a-	2*
Init*	-a-
S = "ab"		1	-b-	2*
Init*	-a-
\			/
\------b------/
S = "aaa"		1*	-a-	2* -a-		3*
Init*	-a-
S = "aba"		1*	-b-	2	-a-	3*
Init*	-a-
\				/
\-------b------/
S = "abb"		1	-b-	2	-b-	3*
Init*	-a-
\		4*	-----b-----/			/
\--b--
S = "abbb"		1	-b-	2	-b-	3*
Init*	-a-
\		4* -b- 5* -b-/				/
\--b--

Анализ суффиксного автомата

Проведём сначала анализ суффиксного автомата.

Во-первых, в нём не может быть циклов, потому что в противном случае автомат бы распознавал слова бесконечной длины, которые никак не могут быть суффиксами строки S.

Во-вторых, число состояний в нём не более 2N-1 (за исключением N=1 и N=2, для них будет 1 и 3

состояния соответственно); этот факт мы пока примем без доказательства, он будет вытекать из корректности описанного ниже алгоритма построения суффиксного автомата.

В-третьих, число переходов - не более 3N-4 (за исключением, опять же, N=1 и N=2); доказательство этого факта мы также приведём после описания самого алгоритма.

Таким образом, мы обнаружили удивительный факт: суффиксный автомат имеет размер O (N), несмотря

на то, что суммарная длина всех суффиксов строки есть величина O (N2). Более того, ниже будет будет описан алгоритм, строящий суффиксный автомат также за линейное время (правда, с потреблением памяти O (N K); если же необходимо экономно использовать память - O (N), то время работы алгоритма увеличивается до O (N log K); более подробно см. в следующем разделе).

Рассмотрим теперь наихудшие тесты для суффиксного автомата. Несложно заметить, что для строки вида "abbb..." будет достигаться наибольшее число состояний. Также непосредственной проверкой можно убедиться в том, что строка вида "abbb...bbbc" является наихудшей с точки зрения количества переходов.

Построение суффиксного автомата

Для описания алгоритма нам потребуется ввести ещё две дополнительных характеристики для каждого состояния: length

и link.

Для некоторого состояния p величина length равна длине наидлиннейшего пути из Init в p. Иными словами, length - это длина наидлиннейшего слова, под воздействием которого автомат из состояния Init переходит в состояние p.

Суффиксная ссылка link для состояния p определяется следующим образом. Рассмотрим наидлиннейший путь из состояния Init в p, ему соответствует некоторая строка. Суффиксная ссылка не определена только для

начального состояния Init. Найдём такой наибольший суффикс этой строки, что ему (этому суффиксу) соответствует некоторое состояние q, отличное от p. Из самого определения следует, что суффикс может быть только собственным, а length[p] > length[q].

Сразу же определим понятие суффиксного пути для некоторого состояния p. Суффиксный путь -

это последовательность (p, link[p], link[link[p]], ...), конечная (поскольку длины length вдоль пути строго убывают, и при этом они всегда неотрицательны). Легко понять, что суффиксный путь всегда завершается состоянием Init. Если для некоторого состояния p мы будем двигаться по его суффиксному пути, то мы будем фактически двигаться

по суффиксам строки, соответствующей состоянию p.

Теперь опишем сам алгоритм. Он будет итеративным (в режиме on-line), т.е. сначала создаст автомат для пустой строки, а потом будет последовательно добавлять символы строки S, перестраивая автомат.

Единственное исключение - что метки "терминальный" будут расставляться за O (N) уже после построения автомата для всей строки.

Введём сразу тип данных "состояние автомата", где таблицу переходов представим для каждого состояния в виде массива величиной K. Состояния будем хранить для удобства в виде статического массива размером MAXLEN*2-1 (где MAXLEN - заранее известная константа - ограничение на длину строки), хотя, понятно, легко будет исправить весь код на использование динамического vector.

const int MAXLEN = ...; // максимальная длина строки const int K = ...; // размер алфавита

struct state {

int length, link; int next[K]; bool termimal;

};

state st[MAXLEN*2-1]; int sz = 0;

int last; // указывает на "последнее" состояние, т.е. то, в которое ведёт самый длинный путь из Init

Итак, сначала создадим суффиксный автомат для пустой строки, он состоит только из начального состояния Init (у него будет номер 0 в массиве st):

st[0].length = 0; st[0].link = -1;

memset (st[0].next, -1, sizeof st[0].next); // делаем все next == -1 ++sz;

last = 0;

Итак, пусть теперь автомат уже построен для некоторой строки W, и мы хотим перестроить его для строки S = W+C, где C - некоторый символ. Реализуем эту операцию в виде функции sa_extend (char c).

Создадим сразу новое состояние nlast, которому по окончании работы sa_extend будет соответствовать строка S. Пока что у этого состояния мы знаем только длину length и то, что переходов из него не будет:

void sa_extend (char c) { int nlast = sz++;

st[nlast].length = st[last].length + 1;

memset (st[nlast].next, -1, sizeof st[nlast].next);

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

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

int p = last;

for (; p!=-1 && st[p].next[c]==-1; p=st[p].link) st[p].next[c] = nlast;

Теперь у нас есть два случая: 1) если мы ни разу не столкнулись с уже существующим переходом, тогда p==-1, и 2) если остановились на таком переходе.

Случай 1) - самый простой. Он означает, что символ C ещё ни разу не встретился в строке W. Мы добавили переходы из каждого суффикса строки W по символу C в строку S, больше нам никаких переходов добавлять не нужно. Осталось только установить суффиксную ссылку для состояния nlast, но она будет указывать, очевидно, на Init (это как раз следует из того, что символ C встретился нам впервые). Итак, мы можем реализовать этот случай:

if (p == -1) st[nlast].link = 0;

else {

Случай 2) распадается также на два случая 2а и 2б. Итак, мы остановились на состоянии p, из которого уже есть переход по символу С, обозначим через q состояние, в которое ведёт этот переход. Если length[p] + 1 == length[q], то это случай 2а, иначе случай 2б (сейчас мы поймём смысл этого равенства).

Случай 2а), т.е. length[p] + 1 == length[q] (в этом случае говорят, что переход из состояния p в состояние

q "сплошной" (solid)). Обозначим через U длиннейшую строку, соответствующую состоянию p (т.е. U.length() == length [p]). Строка U+C является наидлиннейшим суффиксом строки S = W+C, встречающимся в W (иное и

невозможно, поскольку тогда бы мы раньше обнаружили существующий переход по символу C), а потому мы должны провести суффиксную ссылку в то состояние, которому соответствует строка U+A и при этом

является наидлиннейшей для него. Вспоминая, что length[q] == length[p] + 1 == (U+C).length(), мы как раз и получаем, что строка U+C является наидлиннейшей для состояния q, и мы можем провести суффиксную ссылку из состояния nlast в состояние q. Наконец, можно утверждать, что больше никаких переходов добавлять не надо - строка U+C вместе

со всеми своими суффиксами уже была обработана ранее (ведь она уже присутствовала в W).

int q = st[p].next[c];

if (st[p].length + 1 == st[q].length)

st[nlast].link = q;

else {

Случай 2б), т.е. length[p] + 1 != length[q] (из вышеописаных свойств можно утверждать, что length[p] + 1 < length[q]).

Снова, как и в случае 2а), обозначим через U длиннейшую строку для состояния p. Снова мы утверждаем, что строка U +C является наидлиннейшим суффиксом строки S, встречающимся в W, а потому суффиксную ссылку из состояния nlast нам хотелось бы провести в состояние, где эта строка U+C является длиннейшей. Однако на этот раз

такого состояния не существует: length[q] > length[p] + 1 == (U+C).length(), и при этом самой строке U+C соответствует состояние q. Тут нам приходится выполнить более хитрое преобразование автомата - мы вынуждены расщепить состояние q на два состояния, для одного из которых строка U+C будет длиннейшей. Создадим новое состояние clone, и перенаправим в него часть переходов в q. Нам нужно перенаправить переходы, соответствующие строке U+C и всем её суффиксам (точнее говоря, всем суффиксам строки U и плюс символ C). Вспоминая, что строке U как раз соответствует состояние p, и вспоминая понятие суффиксного пути,

мы получаем такую формулировку: продолжим двигаться по суффиксному пути состояния p, и, пока есть переход из него в состояние q по символу C, будем перенаправлять этот переход на состояние clone. Теперь разберёмся с

новым состоянием clone, нам же нужно заполнить его параметры. Его длина length равна длине строки U+C, т.е. length[p] + 1. Его суффиксная ссылка ведёт туда, куда вела суффиксная ссылка состояния q. Наконец, переходы из clone

надо скопировать из состояния q (отсюда и название состояния - "clone"). Осталось только заметить, что суффиксная ссылка для состояния q теперь изменится - она будет указывать, разумеется, на состояния clone (ведь мы отделили строки U+C и короче неё, вот на них теперь и будет указывать суффиксная ссылка). Ну и, разумеется, суффиксная ссылка для состояния nlast будет также указывать на clone (для чего собственно и выполнялось это расщепление).

int clone = sz++;

st[clone].length = st[p].length + 1;

memcpy (st[clone].next, st[q].next, sizeof st

[clone].next);

st[clone].link = st[q].link;

for (; p!=-1 && st[p].next[c]==q; p=st[p].link) st[p].next[c] = clone;

st[q].link = st[nlast].link = clone;

}

}

Наконец, завершаем функцию sa_extend, не забывая обновить значение last:

last = nlast;

}

Теперь осталось только научиться проставлять значения terminal (правда, при решении большинства задач эти значения просто не нужны). Это очень легко сделать: рассмотрим состояние last и его суффиксный путь.

Этим состояниям как раз и соответствуют строка S и все её суффиксы, причём только они (это следует непосредственно из определения суффиксной ссылки):

for (int p=last; p!=-1; p=st[p].link) st[p].terminal = true;

Анализ алгоритма

Приведём сначала обещанные доказательства того, что состояний в суффиксном автомате не более 2N-1, а переходов - 3N-4 (для N>=3).

Оценка на число состояний непосредственно вытекает из корректности алгоритма - мы добавляем одно состояние Init при создании, и добавляем на каждом шаге по одному или двум состояниям; при этом сразу два состояния могут быть добавлены только начиная с третьего шага; итого и получается 1 + N + N-2 = 2N-1.

Оценим теперь максимальное число переходов. Рассмотрим остовное дерево из длиннейших путей в

автомате, начинающихся в вершине Init. Оно будет содержать только сплошные рёбра (причём всех их), и их будет на единицу меньше, чем число состояний. Теперь оценим число несплошных рёбер. Поставим каждому

несплошному ребру из p в q по символу C такую строку: U+C+V, где U - строка, соответствующая длиннейшему пути из Init в p, V - строка, соответствующая длиннейшему пути из q в некоторое терминальное состояние. Заметим, что разным несплошным рёбрам будут соответствовать разные строки U+C+V. С другой стороны, в силу самого построения этой строки, эта строка U+C+V будет суффиксом строки S. Поскольку число различных суффиксов есть N+1, а суффиксы S и "" не могли быть учтены (потому что они входят в остовное дерево), то в итоге несплошных рёбер

не более N-1. Складывая количества сплошных и несплошных рёбер, получаем оценку 3N-4.

Оценим теперь асимптотику алгоритма. Нам нужно оценить суммарное время работы двух циклов for внутри функции sa_extend. С первым циклом всё понятно - на каждой своей итерации он добавляет новый переход, а т.к. число переходов есть O (N), а переходы никогда не удаляются, то суммарное время работы первого цикла есть O

(N). Второй цикл так оценить не получится, поскольку он новых переходов не добавляет. Обозначим через

V наидлиннейшую строку, соответствующую состоянию p. Перед выполнением итерации этого цикла V является K- ым (K>=2) элементом в суффиксном пути W, а после него V+C является 2-ым элементом в суффиксном пути W+C, и потому позиция V как суффикса W строго увеличивается на каждой итерации этого цикла, причём не только в пределах одного вызова функции sa_extend, а в пределах всех вызовов. Потому число выполнений этого цикла также равно O (N).

Итак, если переходы next хранить в виде массива, то получаем асимптотику алгоритма O (N K) (хотя и с очень малой константой, т.к. все действия, за исключением копирования массивов memcpy, выполняются за O (N)), но при использовании памяти O (N K).

Впрочем, на массивах можно достичь и настоящей линейной асимптотики, если вдобавок к массивам хранить списки переходов (в виде vector< pair<char,int> >). Тогда копирование переходов будет осуществляться за O() от количества переходов из текущего состояния, а не за O (K).

Однако, если хранить переходы сжато, например, в виде map<char,int>, то время работы алгоритма увеличится до O (N log K), но зато уменьшится используемая память до O (N).

Реализация

Поскольку весь приведённый выше код равномерно "размазан" по тексту, приведём здесь полную реализацию (работающую за O (N K) (как уже говорилось, на пратике - близко к O (N), поскольку O (N K) операций связаны с копированием массивов вызовами memcpy, которые выполняются очень быстро) при потреблении памяти O (N K):

const int MAXLEN = ...; // максимальная длина строки const int K = ...; // размер алфавита

struct state {

int length, link; int next[K]; bool termimal;

};

state st[MAXLEN*2-1]; int sz, last;

void init() { /*

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

sz = last = 0;

for (int i=0; i<MAXLEN*2-1; ++i) st[i].terminal = false;

st[0].length = 0; */

st[0].link = -1;