Изменения
Новая страница: «{{Определение |definition= Пусть дана строка <tex>S</tex>, <tex>|S| = m</tex>. Суффиксное дерево <tex>T</tex> для стр…»
{{Определение
|definition=
Пусть дана строка <tex>S</tex>, <tex>|S| = m</tex>. Суффиксное дерево <tex>T</tex> для строки <tex>S</tex> - ориентированное дерево с корнем, имеющее ровно <tex>m</tex> листьев, занумерованных от <tex>1</tex> до <tex>m</tex>. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки <tex>S</tex>. Никакие две дуги не могут иметь пометок, начинающихся с одного и того же символа.
}}
Главная особенность суффиксного дерева заключается в том, что для каждого листа <tex>i</tex> конкатенация меток дуг на пути от корня к листу <tex>i</tex> в точности составляет суффикс строки <tex>S</tex>, который начинается в позиции <tex>i</tex>, то есть <tex>S[i..m]</tex>.
Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>S</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>. Во избежание этого в конце строки <tex>S</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило в качестве защитного символа используется <tex>\$</tex>.
|definition=
Пусть дана строка <tex>S</tex>, <tex>|S| = m</tex>. Суффиксное дерево <tex>T</tex> для строки <tex>S</tex> - ориентированное дерево с корнем, имеющее ровно <tex>m</tex> листьев, занумерованных от <tex>1</tex> до <tex>m</tex>. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки <tex>S</tex>. Никакие две дуги не могут иметь пометок, начинающихся с одного и того же символа.
}}
Главная особенность суффиксного дерева заключается в том, что для каждого листа <tex>i</tex> конкатенация меток дуг на пути от корня к листу <tex>i</tex> в точности составляет суффикс строки <tex>S</tex>, который начинается в позиции <tex>i</tex>, то есть <tex>S[i..m]</tex>.
Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>S</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>. Во избежание этого в конце строки <tex>S</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило в качестве защитного символа используется <tex>\$</tex>.
