Он пока еще не проверен уже проверен и работает с точностью до скорости ввода. Задача: отвечать на запросы: ? строка - есть ли такая подстрока в тексте, 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, идем по ребру, ничего не делаем. |  |
Comments (0)
