Изменения

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

Суффиксный бор

13 байт убрано, 06:41, 27 июня 2011
Нет описания правки
'''Суффиксный бор''' (suffix trie) - [[бор]], содержащий все суффиксы данной строки.
По определению, в суффиксном боре для строки <tex>s</tex>, <tex>|s|=n</tex> содержатся все строки <tex>s[1..n], ..., s[n..n]</tex>. Сделаем следующее наблюдение: если в суффиксном боре находится строка <tex>s[i..n]</tex>, то все символы строк вида ее префиксы <tex>s[i..j], i \le j \le n</tex> уже содержатся в нашем боре. Значит, суффиксный бор можно использовать для поиска всех подстрок строки <tex>s</tex> (чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>).
==Свойства==
322
правки

Навигация