Блог пользователя adamant

Автор adamant, 10 лет назад, По-русски

Всем привет! 2 года назад Logvinov_Leon поинтересовался у сообщества о существовании способа перевести суффиксный автомат в суффиксный массив. Ответа, как ни странно, он не получил. Но, так как я, как вы, возможно, заметили, люблю переводить одни строковые структуры в другие, я решил эту тему добить.

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

Но, конечно же, он нас не устраивает и мы хотим пойти дальше. Чтобы время работы было линейным, нам нельзя игнорировать массив used. Легко заметить, что даже так, начав обход в глубину мы точно встретим несколько (как минимум, один) суффикс до того, как впервые второй раз зайдём в посещённое состояние. Теперь наша задача при повторном посещении состояния быстро получить все суффиксы, которые за ним скрываются, не обойдя целиком все пути от состояния до конца. Я предлагаю следующее решение: давайте для каждого состояния в автомате поддерживать индексы первого и последнего встреченного после него суффиксов в суффиксном массиве. Тогда, если мы пришли в used-состояние, мы сразу добавляем в массив все суффиксы, в которые мы бы из него попали с учётом уже пройденной длины. Очевидно, что такое решение будет работать за O(n), так как суффиксов мы суммарно добавим ровно n, а всё остальное время мы просто обходим суффиксный автомат в глубину.

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

  • Проголосовать: нравится
  • +68
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

а без мапа ускоряется?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну... unordered_map здесь не подойдёт, нам нужна упорядоченность. А иначе у нас будет O(nk), что в общем-то не очень хорошо.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      алфавит был 26.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Наверняка можно значительно ускорить, если переписать вектора на массивы. Но насколько — вопрос открытый :)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Блин, вы чего?) То, что я рассказываю настолько очевидно или настолько неинтересно? Хоть бы прокомментировал кто.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Вот мне, например, неинтересно. Как по мне, пост стоит называть "о, смотрите, я понял, что такое суффиксный автомат, суффиксное дерево и какая между ними разница". Ну да, понял, молодец, но зачем сразу об этом пост пилить?) Что до самого "алгоритма", то он чуть менее, чем полностью бесполезен, ты же сам понимаешь.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      Ну, хоть что-то.

      Когда пилю посты, ориентируюсь очень эгоистичным критерием — чем-то вроде "мне это было бы интересным/полезным". Лично я раньше нигде прямого перехода от автомата к массиву не встречал, вот и решил написать. Мне эта тема интересна.

      В любом случае, спасибо за отзыв.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Меня первый раз упомянули в посте. Но всем пофиг.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А мне нравятся такие посты, спасибо adamant за информацию

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

adamant, у тебя довольно интересные посты, но, как мне кажется, люди, которые способны оценить реальную полезность того, что ты пишешь, без труда и сами могут это вывести. Скажем, алгоритм перевода суффиксного массива в суффиксное дерево довольно тривиально придумывается, но всё равно довольно редко применим на практике. Например, в последний раз, когда мне нужно было посчитать динамику на суффиксном дереве, этот алгоритм TL-ился на строке 3*10^5 при построении за O(n log n). Плюс сколько я мучился, пока отлаживал. Но а вообще, я яро плюсую твои посты, потому что я считаю, что это довольно полезные задачки для строковых структур, и потому что я люблю эти структуры:)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо, рад, что посты находят своего читателя :)

    А можешь рассказать, что за задача?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      https://www.hackerrank.com/contests/feb14/challenges/two-strings-game

      Так же решается суффиксным автоматом. Если запихнешь, будет классно)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        1. Стандартной динамикой по автомату посчитаем для каждого состояния обеих строк его выигрышность/проигрышность. Как обычно, состояние выигрышное, если из него есть дуга в проигрышное и проигрышное в противном случае.
        2. Посчитаем для каждого состояния в первом автомате количество выигрышных состояний, в которые мы можем попасть из него. Т.е., это количество подходящих ему состояний во втором автомате + ответ по всем состояниям, в которые из нашего состояния в первом автомате можно попасть.
        3. Наконец, получим ответ. В любой момент мы знаем лексикографические номера состояний, которые можем получить в потомках. Исходя из этого либо переходим в следующее состояние, либо, если искомая позиция находится в этом состоянии, идём искать ему пару во втором автомате.

        По идее должно работать. Код ещё не писал, постараюсь сегодня этим заняться.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          Абсолютно аналогичное решение будет с суффиксным деревом.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А, блин, просто проксорить недостаточно(

        Похоже, там какая-то ведическая магия

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    Вероятно, я не один такой.

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

2 years ago Logvinov_Leon asked about way to get the suffix array from suffix automata. Oddly enough, he had not received answer.