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

Код Укконена (теперь с картинками)
Автор freopen, 14 лет назад, По-русски

Он пока еще не проверен уже проверен и работает с точностью до скорости ввода. Задача: отвечать на запросы: ? строка - есть ли такая подстрока в тексте, A строка - добавить строку в текст (приписать в конец). Публикую код в том виде, в котором мне его удобно отлаживать. Да, я разбираюсь в этом коде, а если наставить переносов, я разбираться в нем перестану. Если расставить переносы, получится около 35-40 строчек, что много, т.к. я не все фишки вспомнил. Может вспомню и добавлю еще. А теперь, собственно, сам код.

КОД УККОНЕНА (с комментариями)


Написать и сдать своего Укконена вы можете здесь: http://yeputons.net/tsweb/ в контесте "Сборная солянка, 5 мая 2011 года".
А вот и обещанные рисунки. Тест - abbbab.

Добавляем букву a, создаем новую вершину, переходим к суффиксу (пустая строка).
 
Добавляем букву b, создаем новую вершину, переходим к суффиксу (пустая строка).
 
Добавляем b, идем по ребру, ничего не делаем.

Добавляем b, идем по ребру, ничего не делаем.
 
Добавляем a, разделяем ребро 0->3 вершиной 4, создаем лист 5, вешаем туда текущий суффикс.

Ищем суффиксную ссылку, она ведет в середину ребра 0->4, разделяем ребро 0->4, ставим вершину 6.

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

Добавляем b, идем по ребру, ничего не делаем.

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

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

O_O

харош! ))))

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Вторую версию кода можно и на e-maxx положить (если требуется, конечно).
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      тогда конечно положим, нельзя, чтобы такое затерялось :)

      больше оптимайзов по размеру не ожидается? ("... т.к. я не все фишки вспомнил")

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вот, еще чуть-чуть поправил. Остальное совсем не помню :(. Больше оптимайзов, видимо, не будет.
        → Ответить
14 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Кстати, вдруг кому-то это поможет с отладкой Укконена: мне очень помогал тест:
A abbab
? bab
? bbab
? abbab

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    В моем коде он покрывает весь код, кроме одного места: else s[ts-2]=ts;
    Это место сложно покрыть коротким тестом, т.к. это условие обрабатывает случай, когда надо поставить суффиксную ссылку в еще не существующую вершину. Можно на этот случай добавить такой тест:

    A aaab
    ? ab
    ? aab
    ? aaab
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      Обобщая все вышесказанное, предлагаю такой тест:
      A abbbab
      ? bab
      ? bbab
      ? bbbab
      ? abbbab

      Если хождение по суффиксному дереву реализованы верно, то этот тест должен отловить 99% ошибок. Надо будет еще нарисовать схемы суффиксного дерева.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Мне кажется, или раньше(давно, когда ты рассказывал) код у тебя был короче, квадратней, и было больше goto?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Короче - да, после разворота по одной операции получалось ~20 строк. Квадратнее - не знаю, не помню. Больше goto - нет, goto было ровно два. Здесь у goto четкая цель выполнять переход к суффиксу. Этих переходов - 2 за алгоритм.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Наконец-то у меня дойдут руки разобраться и изучить этот замечательный алгоритм. Спасибо!
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
О, Grand Merci, теперь наконец-то будет не лень освоить данный алгоритм!
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ты ведь помнишь, что размер дерева может быть ~2N, где N - длина строки, просто у тебя их размеры равны)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, кто-нибудь знает задачу, которая деревом решается проще, чем автоматом?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Таких много. Например, построить суффиксный массив из дерева проще чем из автомата. 
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Строить массив из дерева - это как же надо не любить строить массив обычными методами, к тому же массив был создан для экономии места и времени при больших алфавитах!
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну я, действительно, не очень удачный пример назвал, это не применить на практике. Но деревом не сложнее решить почти любую задачу.
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
наибольший общий палиндром K строк?
→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Вот строю я дерево для строки aaaab этим кодом. Почему из вершин, соответствующим строкам ab, aab, aaab, aaaab суффсылки ведут в 0, а не в друг-друга поочереди?

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

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

    Для промежуточных вершин суфссылка очевидно определена всегда, т.к. если у нас есть строчки ab...zx и ab...zy, то и строчки b...zx и b...zy тоже есть из чего следует, что существование вершины для ab...z влечет сущестование вершины для b...z.

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

Что Вы посоветуете использовать дерево, массив или автомат, что по-Вашему наиболее удобная и полезная структура?

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

    То, что быстрее пишется в контексте данной задачи. Чаще всего это автомат.

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

Ни картиночек, ни кода. Время ничего не щадит :(

→ Ответить