Он пока еще не проверен уже проверен и работает с точностью до скорости ввода. Задача: отвечать на запросы: ? строка - есть ли такая подстрока в тексте, 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, идем по ребру, ничего не делаем. |  |
O_O
харош! ))))
тогда конечно положим, нельзя, чтобы такое затерялось :)
больше оптимайзов по размеру не ожидается? ("... т.к. я не все фишки вспомнил")
A abbab
? bab
? bbab
? abbab
Это место сложно покрыть коротким тестом, т.к. это условие обрабатывает случай, когда надо поставить суффиксную ссылку в еще не существующую вершину. Можно на этот случай добавить такой тест:
A aaab
? ab
? aab
? aaab
A abbbab
? bab
? bbab
? bbbab
? abbbab
Если хождение по суффиксному дереву реализованы верно, то этот тест должен отловить 99% ошибок.
Надо будет еще нарисовать схемы суффиксного дерева.Вот строю я дерево для строки
aaaabэтим кодом. Почему из вершин, соответствующим строкамab,aab,aaab,aaaabсуффсылки ведут в 0, а не в друг-друга поочереди?Надеюсь, что ответ через три месяца все еще актуален. В суффиксном дереве обычно не определяется суффиксная ссылка для листьев просто потому что не всегда существует вершина, в которую она должна бы вести. Например, для дерева строки
aaдля строкиaaсуффиксная ссылка должна бы вести в строкуa, однако вершины для этой строки нет.Для промежуточных вершин суфссылка очевидно определена всегда, т.к. если у нас есть строчки
ab...zxиab...zy, то и строчкиb...zxиb...zyтоже есть из чего следует, что существование вершины дляab...zвлечет сущестование вершины дляb...z.Что Вы посоветуете использовать дерево, массив или автомат, что по-Вашему наиболее удобная и полезная структура?
То, что быстрее пишется в контексте данной задачи. Чаще всего это автомат.
Ни картиночек, ни кода. Время ничего не щадит :(
Грустно. Код все еще жив здесь: http://e-maxx.ru/algo/ukkonen в самом низу. Картинки потерялись :(.
Некоторые картинки можно достать тут http://web.archive.org/web/20110526094140/http://www.codeforces.com/blog/entry/1850