275
правок
Изменения
м
== Реализация алгоритма за O(n<sup>3</sup>) ==
for i = 1 .. n
for j = 1 .. i
спускаемся от корня до конца текущего <tex>j</tex>-го суффикса
совершаем продление по одному из правил символом <tex>s_{i}</tex>
Нет описания правки
'''Замечание:''' Казалось бы, что можно просто добавлять все суффиксы строки в дерево по очереди, и это уже было бы <tex>O(n^2)</tex>. Но оптимизировать такой квадратичный алгоритм до линейного немного сложнее, хотя именно это и делает [[алгоритм МакКрейта]]. Оптимизируя описанный выше алгоритм, мы получим более простой алгоритм за <tex>O(n)</tex>.
== Продление суффиксов ==
|style="background:#ffffff"|[[Файл:ExampleUkkonen6.png|300px]]
|}
== Реализация алгоритма за O(n<sup>3</sup>) ==
for i = 1 .. n
for j = 1 .. i
спускаемся от корня до конца текущего <tex>j</tex>-го суффикса
совершаем продление по одному из правил символом <tex>s_{i}</tex>
==Суффиксные ссылки==
