\Section{Суффиксное дерево. Алгоритм Укконена.}{26 апреля}{Шевченко Илья}

\Subsection{Суффиксный бор, дерево}

\begin{Def}
	Суффиксный бор - бор всех суффиксов строки.
\end{Def}
\begin{Def}
	Сжатый бор - бор, в котором у всех вершин, кроме листов есть хотя бы два сына. 
	При этом на рёбрах теперь написаны не буквы, а строки.
\end{Def}
\begin{Def}
	Суффиксное дерево - сжатый суффиксный бор.
\end{Def}

\begin{Lm}
	Если сделать из строки $s$ строку $s\#$, где $\#$ - символ, который не встречается 
	в строке, то все её суффиксы будут заканчиватся в листах.
\end{Lm}

\Subsection{Элементарный алгоритм построения}

Рассмотрим следующий алгоритм построения суффиксного дерева за $\O(n^2)$.
\begin{lstlisting}
for(i,n)
  Add(s[i:n])
\end{lstlisting}
Где $Add$ - функция, которая за линию спускается по дереву добавляя суффикс.
\begin{Lm}
	$SuffTree(s)$ содержит не более $2|s|$ вершин.
\end{Lm}
\begin{proof}
	Новые вершины создаются, только когда $Add$ в процессе спуска не может перейти 
	по очередному символу. В этот момент создаётся не более двух вершин. Первая в середине 
	ребра, если в момент неудачи функция стояла посередине ребра и вторая - вершина-конец 
	суффикса.
\end{proof}

Техническая деталь: позицию в дереве хранить удобнее всего как пару $(e,x)$ - номер ребра, 
и позицию на нём.

\Subsection{Алгоритм Укконена}

Внимательно посмотритм на жизненный цикл суффикса в суффиксном дереве:
\begin{enumerate}
	\item Рождение суффикса в корне дерева.
	\item Спуск конечной вершины суффикса по дереву.
	\item Разветвление суффикса в момент, когда дальнейший спуск невозможен.
	\item Свободное произрастание в личине листа дерева.
\end{enumerate}

\Subsubsection{Реализация алгоритма Укконена за $\O(n^2)$}

На каждом шаге будем поддерживать суффиксное дерево строки $s[0:i]$. 
Будем помнить позиции концов всех суффиксов в дереве. При добавлении символа 
будем пытаться продлить каждый суффикс на этот символ. Если надо будем разветвляться.

\Subsection{Улучшение до $\O(n)$}

\begin{Lm}
	Если в ребро ведущее в лист написать либо $[l,inf)$, либо $[l,\&n]$, то они будут 
	расти сами без нашего вмешательства.
\end{Lm}
\begin{Lm}
	Суффикс $s[i:n]$ находится в состоянии (2) $\Rightarrow \forall j>i~s[j:n]$ тоже в 
	состоянии (2).
\end{Lm}
\begin{proof}
	Если бы какой-то более короткий суффикс ответвился по символу, то данный длинный 
	суффикс бы тоже ответвился.
\end{proof}

Это подталкивает нас к мысли следить только за самым длинным неразветвившимся суффиксом.
Получается следующий алгоритм:
\begin{lstlisting}
suffarr(){
	for(i,n)
		addchar(s[i])
addchar(c){
x:
	if succesful descend with char c
		pass
	else
		create new vertex
		switch to next suffix
		goto x
}
\end{lstlisting}

Осталось объяснить что такое $switch~to~next~suffix$. Это значит уменьшить на единичку 
длину текущего суффикса, за которым мы следим и перейти к нему в дереве.

Как же мы перейдём в дереве? Поднимемся до вершины из которой исходит ребро, на котором 
мы стоим. Перейдём по суффиксной ссылке. Эта суффиксная ссылка обязательно 
ведёт в вершину, т.к. если подстрока кончается в вершине суфф. дерева, то 
её суффиксы тоже кончаются в вершинах. Теперь спустимся вниз на строку, на которую 
поднялись. Спускаться будем не по каждому символу отдельно, а быстро по рёбрам. 

А ещё в какой-то момент нужно пересчитать суффиксные ссылки свежесозданных вершин. 
Например, можно при спуске сложить все вершины на стек, а потом проставить ссылки 
разматывая этот стек.

Теперь нужно оценить временную сложность всех наших спусков.

\begin{Lm}
	Все спуске в сумме отработают за $\O(n)$.
\end{Lm}
\begin{proof}
	Рассмотрим потенциал $\phi(v)=$ количеству вершин на пути от корня до $v$. 
	$phi(v)\leq n$. С другой стороны, за каждый спуск к следующему суффиксу потенциал 
	может уменьшиться не более, чем на 1. Т.е. $phi(v)-1\leq phi(suf(v))$. 
	Это так, потому что суффиксная ссылка из каждой вершины ведёт в свою вершину, 
	кроме, возможно, самой неглубокой вершины из которой ссылка может вести в корень.
\end{proof}