Изменения

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

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

Нет изменений в размере, 13:42, 1 июня 2012
Определение
==Определение==
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} дерево с <tex>n</tex> листьями, каждая внутренняя вершина которого имеет не меньше двух детей, а каждое ребро помечено непустой подстрокой строки <tex>s</tex> и символом ее начала. Два ребра, выходящие из одной вершины, не могут иметь одинаковых символьных метокподстрок, начинающихся с одного и того же символа.
Такое дерево, как и суффиксный бор, содержит все суффиксы строки <tex>s</tex>, причем каждый суффикс заканчивается точно в листе и нигде кроме него.
80
правок

Навигация