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

---

Суффиксное дерево — бор, построенный на всех суффиксах некоторой строки. Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w.

Лемма.Местоположение w явно в компактном суффиксном дереве тогда и только тогда, когда w является не вложенным суффиксом t или w — правое ветвление.

Доказательство.${\displaystyle \Rightarrow }$. Если ${\displaystyle {\overline {w}}}$ явно, то это может быть либо лист, либо вершина ветвления или корень (в этом случае ${\displaystyle w=\varepsilon }$ и w — вложенный суффикс t).

Если ${\displaystyle {\overline {w}}}$ — лист, тогда также является и суффиксом t. Значит, это должен быть не вложенный суффикс, так как иначе он появился бы где-нибудь ещё в строке t: ${\displaystyle \exists }$ v — суффикс t такой, что w — префикс v. Этот узел не может быть листом.

Если ${\displaystyle {\overline {w}}}$ — узел ветвления, тогда должны существовать, по меньшей мере, два выходящих ребра из ${\displaystyle {\overline {w}}}$ с различными метками. Это означает, что существуют два различных суффикса u, v, что w — префикс u и w — префикс v, где v = wxs, u = ${\displaystyle wx's'}$, x ${\displaystyle \neq x'}$. Следовательно, w — правое ветвление.

${\displaystyle \Leftarrow }$. Если w является не вложенным суффиксом t, это должен быть лист. Если w — правое ветвление, то имеются два суффикса u и v, u = wxs, v = ${\displaystyle wx's'}$, x ${\displaystyle \neq x'}$, тогда w является узлом ветвления.Лемма доказана.

---