e-maxx_algo

по суффиксному автомату и наоборот

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

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

суффиксный автомат, построенный для строки , — это суффиксное дерево строки .

Введём понятие расширяющей ссылки: зафиксируем вершину суффиксного дерева и символ ; тогда расширяющая ссылка ведёт в вершину дерева, соответствующую строке (если этот путь

оканчивается посередине ребра, то проведём ссылку в нижний конец этого ребра); если такого пути вообще нет в дереве, то расширяющая ссылка не определена. В некотором смысле, расширяющие ссылки противоположны суффиксным ссылкам.

Теорема 1. Дерево, образованное суффиксными ссылками в , является суффиксным деревом .

сплошные рёбра в — это инвертированные суффиксные ссылки в .

Эти две теоремы позволяют по одной из структур (суффиксному дереву или суффиксному автомату) построить другую за время — эти два простых алгоритма будут рассмотрены нами ниже в теоремах 3 и 4.

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

и его дерево суффиксных ссылок (для наглядности мы подписываем каждое состояние

его -строкой):

:

Лемма. Следующие три утверждения эквивалентны для любых двух подстрок и :

● и лежат на одном и том же пути из корня в суффиксном дереве .

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

Доказательство теоремы 1.

Состояния суффиксного автомата соответствуют вершинам суффиксного дерева.

требовалось доказать.

Доказательство теоремы 2.

Состояния суффиксного автомата соответствуют вершинам суффиксного дерева.

В инвертированной строке это означает, что это такое состояние, которому соответствует подстрока, от которой (в тексте ) совпадает с от подстроки .

Это как раз и означает, что:

Первая часть теоремы доказана, осталось доказать вторую часть: что все сплошные переходы в автомате соответствуют суффиксным ссылкам в дереве. Сплошной переход отличается от несплошного тем,

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

Теорема полностью доказана.

Доказательство теоремы 3.

Суффиксное дерево будет содержать столько же вершин, сколько состояний в , причём

Асимптотика. .

Решение. Построим суффиксный автомат по строке .

В суффиксном автомате любой подстроке строки соответствует какой-то путь в автомате. Поскольку повторяющихся строк в автомате быть не может, то ответ на задачу — это количество различных путей в автомате, начинающихся в начальной вершине .

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

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

т.е. можно выразить как сумму ответов по всевозможным переходам из состояния .

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

Суммарная длина различных подстрок

Условие. Дана строка . Требуется узнать суммарную длину всех различных её подстрок.

Асимптотика. .

Решение. Решение задачи аналогично предыдущей, только теперь надо считать в динамике две величины: количество различных подстрок и их суммарную длину .

Как считать , описано в предыдущей задаче, а величину можно вычислить таким образом:

Наименьший циклический сдвиг

Условие. Дана строка . Требуется найти лексикографически наименьший её циклический сдвиг.

действуем жадно, переходя по переходу с минимальным символом.

Количество вхождений

Условие. Дан текст , и поступают запросы в виде: дана строка , требуется узнать, сколько раз строка входит в текст как подстрока (вхождения могут перекрываться).

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

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

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

Утверждается, что в конце концов мы так посчитаем для каждого состояния правильные значения .

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

Почему тем самым мы не учтём одну и ту же позицию несколько раз? Потому что из каждого состояния его значение "пробрасывается" только один раз, поэтому не могло так получиться, что из одного состояния его значение "пробросилось" до какого-то другого состояния дважды, двумя разными путями.

Таким образом, мы научились считать эти величины для всех состояний автомата.

После этого ответ на запрос тривиален — надо просто вернуть , где — состояние, соответствующее образцу .

Позиция первого вхождения

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

Асимптотика. Препроцессинг и на один запрос.

вхождения. Иными словами, мы хотим найти заранее минимальный элемент каждого из множеств (поскольку явно поддерживать все множества мы не можем).

новое состояние при входе в функцию , то выставляем ему:

Решение. Построим суффиксный автомат по тексту . Аналогично предыдущей задаче, посчитаем в процессе построения автомата для каждого состояния позицию окончания первого вхождения.

Пусть теперь поступил запрос — строка . Найдём, какому состоянию она соответствует.

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

Иными словами, нам требуется найти все состояния, из которых достижимо по суффиксным ссылкам состояние .

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

дважды (потому что из каждого состояния суффиксная ссылка выходит только одна, поэтому не может быть двух путей, ведущих в одно и то же состояние).

Правда, надо учитывать, что у двух состояний их значения могут совпадать: если одно состояние

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

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

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

которых , то мы тем самым получим все требуемые позиций без повторов. Приведём наброски реализации:

struct state {

...

bool is_clon; int first_pos;

vector<int> inv_link;

};

... после построения автомата ...

for (int v=1; v<sz; ++v)

st[st[v].link].inv_link.push_back (v);

...

// ответ на запрос - вывод всех вхождений (возможно, с повторами) void output_all_occurences (int v, int P_length) {

if (! st[v].is_clon)

cout << st[v].first_pos - P_length + 1 << endl; for (size_t i=0; i<st[v].inv_link.size(); ++i)

output_all_occurences (st[v].inv_link[i], P_length);

}

Поиск кратчайшей строки, не входящей в данную

Условие. Дана строка , и задан определённый алфавит. Требуется найти такую строку наименьшей длины, что она не встречается в как подстрока.

Асимптотика. Решение за .

Решение. Решать будет динамическим программирование по автомату, построенному для строки .

Пусть — это ответ для вершины , т.е. мы уже набрали часть подстроки, оказавшись в состоянии , и хотим

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

можем приписать такой символ и выйти за пределы автомата, получив тем самым искомую строку.

В противном случае, одним символом обойтись не получится, поэтому надо взять минимум из ответов по всевозможным символам:

Ответ на задачу будет равен , а саму строку можно восстановить, восстановив, каким образом в динамике получился этот минимум.

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

Условие. Даны две строки и . Требуется найти их наидлиннейшую общую подстроку, т.е. такую строку , что она является подстрокой и , и .

Асимптотика. Решение за .

Решение. Построим суффиксный автомат по строке .

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

Для этого будем поддерживать две переменные: текущее состояние и текущую длину . Эти

две переменные будут описывать текущую совпадающую часть: её длину и состояние, которое соответствует ей

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

Изначально , , т.е. совпадение пустое.

Пусть теперь мы рассматриваем символ и хотим пересчитать ответ для него.

●Если же из состояния нет требуемого перехода, то мы должны попытаться укоротить текущую совпадающую часть, для чего надо перейти по суффиксной ссылке:

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

длины, соответствующая этому состоянию:

Если из нового состояния вновь не будет перехода по требуемому символу, то мы снова должны пройти по суффиксной ссылке и уменьшить , и так далее, пока не найдём переход (тогда перейдём к пункту 1) или мы не попадём

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

Реализация:

string lcs (string s, string t) { sa_init();

for (int i=0; i<(int)s.length(); ++i) sa_extend (s[i]);

int v = 0, l = 0,

best = 0, bestpos = 0;

for (int i=0; i<(int)t.length(); ++i) {

while (v && ! st[v].next.count(t[i])) { v = st[v].link;

l = st[v].length;

}

if (st[v].next.count(t[i])) { v = st[v].next[t[i]]; ++l;

}

if (l > best)

best = l, bestpos = i;

}

return t.substr (bestpos-best+1, best);

}

Наибольшая общая подстрока нескольких строк.

Построим для строки суффиксный автомат.

Теперь нам требуется найти такую строку в автомате, которая содержится во всех строках , и в этом нам помогут добавленные спец. символы. Заметим, что если какая-либо подстрока входит в некоторую строку , то

из которого были найдены пути по всем символам.

Литература

Приведём сначала список первых работ, связанных с суффиксными автоматами:

●A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, R. McConnell. Linear Size Finite Automata for the Set of All Subwords of a Word. An Outline of Results [1983]

●A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler. The Smallest Automaton Recognizing the Subwords of a Text [1984]

●Maxime Crochemore. Optimal Factor Transducers [1985]

●Maxime Crochemore. Transducers and Repetitions [1986]

●A. Nerode. Linear automaton transformations [1958]

Помимо этого, в более современных источниках эта тема затрагивается во многих книгах по строковым алгоритмам:

●Maxime Crochemore, Wowjcieh Rytter. Jewels of Stringology [2002]

●Bill Smyth. Computing Patterns in Strings [2003]

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

Нахождение всех подпалиндромов

Постановка задачи

является палиндромом (т.е. читается одинаково слева направо и справа налево).

Уточнение постановки

соответственно нечётной и чётной длины с центром в позиции .

А в строке есть два палиндрома чётной длины с центром в символе , т.е. значение :

для хранения информации обо всех подпалиндромах этой строки.

Достаточно неожиданным фактом является то, что существует довольно простой алгоритм, который вычисляет эти "массивы палиндромностей" и за линейное время. Этот алгоритм и описывается в данной статье.

Решение

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

Однако описываемый в данной статье метод значительно проще, и обладает меньшими скрытыми константами

васимптотике времени и памяти. Этот алгоритм был открыт Гленном Манакером (Glenn Manacher)

в1975 г.

Тривиальный алгоритм

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

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

Такой алгоритм слишком медленен, весь ответ он может посчитать лишь за время . Приведём для наглядности его реализацию:

vector<int> d1 (n), d2 (n); for (int i=0; i<n; ++i) {

d1[i] = 1;

while (i-d1[i] >= 0 && i+d1[i] < n && s[i-d1[i]] == s[i+d1[i]]) ++d1[i];

d2[i] = 0;

while (i-d2[i]-1 >= 0 && i+d2[i] < n && s[i-d2[i]-1] == s[i+d2[i]]) ++d2[i];

}

Алгоритм Манакера

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

е. подпалиндрома с наибольшим значением ). Изначально можно положить .

● Если не находится в пределах текущего подпалиндрома, т.е. , то просто выполним тривиальный алгоритм.

Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает

позиции подпалиндром имеет такую же длину.

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

увеличить значение , пока это возможно.

Иллюстрация этого случая (на ней палиндром с центром в изображён уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром):

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

внешнего палиндрома, т.е. в область "try moving here".)

Оценка асимптотики алгоритма Манакера

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

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