Изменения

Перейти к: навигация, поиск

Сжатое суффиксное дерево

6 байт убрано, 00:59, 8 марта 2016
→‎Поиск строки максимальной длины, ветвящейся влево и вправо
Если среди левых символов детей <tex>v</tex> нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей.
:'''Случай 2.1.'''Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то записываем в <tex>v</tex> этот символ <tex>x</tex>.
:'''Случай 2.2.'''Если не все левые символы детей <tex>v</tex> эквивалентны, то записываем в <tex>v</tex>, что она различна влево.
Так как время проверки <tex>v</tex> пропорционально числу детей, время работы всего алгоритма {{---}} <tex>O(n)</tex>.
ExileHell
313
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/52542»

Навигация