freopen's blog

By freopen, 8 years ago, In Russian,

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

 
 
 
 
  • Vote: I like it
  • +80
  • Vote: I do not like it