Всем привет! 2 года назад Logvinov_Leon поинтересовался у сообщества о существовании способа перевести суффиксный автомат в суффиксный массив. Ответа, как ни странно, он не получил. Но, так как я, как вы, возможно, заметили, люблю переводить одни строковые структуры в другие, я решил эту тему добить.
Итак, можно заметить, что суффиксный автомат — по сути суффиксное дерево с несколько другим принципом сжатия. Если в сжатом дереве мы просто сжимаем рёбра, то при построении суффиксного автомата у нас выходит что-то, похожее на двусторонний бор. У нас оказываются сжатыми не только общие префиксы, но и общие суффиксы. Отсюда можно сделать следующий интересный вывод: если мы будем обходить автомат, игнорируя то, была ли посещена вершина раньше в лексикографическом порядке, мы получим тот же результат, как если бы мы обходили суффиксное дерево. Теперь вспомним о том, что суффиксный массив из суффиксного дерева получается обычным дфс — мы просто выписываем суффиксы в том порядке, в каком мы их в нём встретим. Таким образом, мы уже имеем алгоритм построения суффиксного массива из автомата за O(n2).
Но, конечно же, он нас не устраивает и мы хотим пойти дальше. Чтобы время работы было линейным, нам нельзя игнорировать массив used. Легко заметить, что даже так, начав обход в глубину мы точно встретим несколько (как минимум, один) суффикс до того, как впервые второй раз зайдём в посещённое состояние. Теперь наша задача при повторном посещении состояния быстро получить все суффиксы, которые за ним скрываются, не обойдя целиком все пути от состояния до конца. Я предлагаю следующее решение: давайте для каждого состояния в автомате поддерживать индексы первого и последнего встреченного после него суффиксов в суффиксном массиве. Тогда, если мы пришли в used-состояние, мы сразу добавляем в массив все суффиксы, в которые мы бы из него попали с учётом уже пройденной длины. Очевидно, что такое решение будет работать за O(n), так как суффиксов мы суммарно добавим ровно n, а всё остальное время мы просто обходим суффиксный автомат в глубину.
P.S. моя реализация алгоритма.
P.P.S. Не могу сказать наверняка, но похоже, что на практике этот алгоритм всё же неприменим из-за очень большой константы.
а без мапа ускоряется?
Ну...
unordered_mapздесь не подойдёт, нам нужна упорядоченность. А иначе у нас будет O(nk), что в общем-то не очень хорошо.ну когда-как. я когда строил по автомату дерево (только переходы по буквам), а по нему пускал дфс, то это работало в 1.75 раз быстрее суфмасса.
алфавит был 26.
Наверняка можно значительно ускорить, если переписать вектора на массивы. Но насколько — вопрос открытый :)
Кстати, можно ещё заметить, что так можно и массив lcp на ходу восстанавливать, т.к. ветвления происходят либо в уже посещённых ранее состояниях, в которые мы входим второй раз, либо в терминальных.
Блин, вы чего?) То, что я рассказываю настолько очевидно или настолько неинтересно? Хоть бы прокомментировал кто.
Вот мне, например, неинтересно. Как по мне, пост стоит называть "о, смотрите, я понял, что такое суффиксный автомат, суффиксное дерево и какая между ними разница". Ну да, понял, молодец, но зачем сразу об этом пост пилить?) Что до самого "алгоритма", то он чуть менее, чем полностью бесполезен, ты же сам понимаешь.
Ну, хоть что-то.
Когда пилю посты, ориентируюсь очень эгоистичным критерием — чем-то вроде "мне это было бы интересным/полезным". Лично я раньше нигде прямого перехода от автомата к массиву не встречал, вот и решил написать. Мне эта тема интересна.
В любом случае, спасибо за отзыв.
Да не, без обид, ты правда молодец, здорово, когда есть такой энтузиазм, возможно, это кому-то ещё будет интересно, я выразил лишь своё мнение о том, как это выглядит со стороны, и легко могу ошибаться.
Меня первый раз упомянули в посте. Но всем пофиг.
А ты вообще кто? Оо
Спасибо
Я рад, что спустя 7 недель комментарий, наконец, оценили по достоинству.
Это была гроссмейстерская пауза
А мне нравятся такие посты, спасибо adamant за информацию
adamant, у тебя довольно интересные посты, но, как мне кажется, люди, которые способны оценить реальную полезность того, что ты пишешь, без труда и сами могут это вывести. Скажем, алгоритм перевода суффиксного массива в суффиксное дерево довольно тривиально придумывается, но всё равно довольно редко применим на практике. Например, в последний раз, когда мне нужно было посчитать динамику на суффиксном дереве, этот алгоритм TL-ился на строке 3*10^5 при построении за O(n log n). Плюс сколько я мучился, пока отлаживал. Но а вообще, я яро плюсую твои посты, потому что я считаю, что это довольно полезные задачки для строковых структур, и потому что я люблю эти структуры:)
Спасибо, рад, что посты находят своего читателя :)
А можешь рассказать, что за задача?
https://www.hackerrank.com/contests/feb14/challenges/two-strings-game
Так же решается суффиксным автоматом. Если запихнешь, будет классно)
Вообще мне так кажется, что задача изначально под суффиксный автомат заточена. Явно, что то, чем закончится игра зависит только от того, в каких состояниях автомата были начальные подстроки, т.к. одно состояние — один правый контекст. Основная проблема, конечно, в том, что строки две. Похоже, что чтобы определить, является ли состояние из двух строк выигрышным, нужно проксорить то, являются ли выигрышными сами строки. Таким образом, для одного отдельно взятого состояния в первой строке мы можем однозначно определить количество и тип (по выигрышности) состояний во второй строке, которые при взятии в пару дадут нам выигрыш. Отсюда следует такой алгоритм:
По идее должно работать. Код ещё не писал, постараюсь сегодня этим заняться.
Абсолютно аналогичное решение будет с суффиксным деревом.
А, блин, просто проксорить недостаточно(
Похоже, там какая-то ведическая магия
С другой стороны — вот я реальную полезность оценить не могу, потому что почти ничего в этом не понимаю, но вижу, что тему обсуждают, плюсуют — значит что-то дельное; вот мне и стимул разобраться, узнать что-то новое, поднять свой уровень.
Вероятно, я не один такой.