Изменения

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но занимающая она занимает много места в памяти. Рассмотрим в боре все такие пути от <tex>u</tex> до <tex>v</tex> в суффиксном боре, в которых каждая вершина имеет у каждой вершины только одного сынаодин сын. Такой путь можно сжать до одного ребра <tex>u v</tex>, пометив его всеми встречающимися записав на нем все встречающиеся на пути символамисимволы. Получившееся дерево носит название Получилось '''сжатое суффиксное дерево'''.

'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} ориентированное дерево с <tex>n</tex> листьями, каждая внутренняя вершина которого имеет не меньше двух детей, а каждое ребро помечено непустой подстрокой строки <tex>s</tex> и символом, с которого начинается эта подстрокаее начала. При этом два Два ребра, выходящие из одной вершины, не могут иметь одинаковых символьных пометокметок. Такое дерево , как и суффиксный бор, содержит все суффиксы строки <tex>s</tex>: для каждого листа <tex>i</tex> конкатенация подстрок на ребрах пути от корня к этому листу составляет суффикс, который начинается в позиции <tex>i</tex>, то есть <tex>s[i..n]</tex>. Иными словами, причем каждый суффикс строки <tex>s</tex> заканчивается точно в листе и нигде кроме листа, как и в суффиксном боренего.

Определение суффиксного дерева не гарантирует, что такое По определению суффиксное дерево существует не для любой строки <tex>s</tex>. Если : если один суффикс строки совпадает с префиксом другого, то построить такое суффиксное дерево, удовлетворяющее данному выше определению, невозможно. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa.</tex> Во избежание этого Для решения проблемы в конце строки <tex>s</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется : '''''защитнымзащитный'''''символ. Как правило, это <tex>\$</tex>. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т.к. он не встречается в строке нигде, кроме позиции последнего символа.

Каждое ребро суффиксного дерева помечается подстрокой исходной строки <tex>s</tex>. Но лучше для него хранить не саму подстроку, а Для хранения на ребре подстроки используют индексы ее начала и конца в исходной строке {{---}} <tex>l, r</tex>. Итак, с каждым ребром дерева ассоциируются две инцидентные ей вершины, символ, с которого начинается подстрока на ребре и два числа <tex>l, r</tex>. Представим дерево как массив <tex>[|V|*|\Sigma|]</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве, <tex>|\Sigma|</tex> - мощность алфавита. Каждая <tex>[i][j]</tex> ячейка массива содержит информацию о том, в какую вершину ведет <tex>i-</tex>ое ребро по <tex>j-</tex>ому символу и индексы <tex>l, r</tex> подстроки на ребре. Очевидно, такое дерево занимает <tex>O(|V||\Sigma|)</tex> памяти.