\subsection{Generalized Suffix Tree}\label{sec:gst}

% Seja $\Sigma = \{\alpha_{1}, \dots,  \alpha_{\sigma} \}$ um alfabeto com $\sigma$ caracteres. 
% Seja $\Sigma^*$ um conjunto com todas as \textit{strings} que podem ser construídas a partir de $\Sigma$ e seja $S \in \Sigma^*$ uma \textit{string} com $m$ caracteres, isto é, $|S| = m$. 
% Seja $S[i:j]$ ($1 \leq i \leq j \leq m$) uma \textit{substring} entre (e inclusive) o i-ésimo e j-ésimo caracteres de $S$.
% Sejam todas as \textit{substrings} $S[1:i]$ prefixos de $S$ e todas as \textit{substrings} $S[i:m]$ sufixos de $S$, denotado por $S[i]$. 
% Seja~\$~$\notin \Sigma$~um caractere terminal que representa o final de uma \textit{string}.
% Seja $T = \{S_1, S_2, \dots, S_n\}$ um conjunto com $n$ \textit{strings}. 

Let $\Sigma = \{\alpha_{1}, \dots,  \alpha_{\sigma} \}$ be an alphabet with $\sigma$ characters.
Let $\Sigma^*$ be the set of all strings generated from $\Sigma$ and let $S \in \Sigma^*$ be a string with $m$ characters ($|S| = m$).
Let $S[i:j]$ ($1 \leq i \leq j \leq m$) be a substring between (and including) the $i^{th}$ and $j^{th}$ characters of $S$.
Let all substrings $S[1:i]$ be prefixes of $S$ and let all substrings $S[i:m]$ be suffixes of $S$, denoted by $S[i]$.
Let \$~$\notin \Sigma$ be a terminal character that represents the end of a string.
Finally, let $T = \{S_1, S_2...,S_n\}$ be a set with $n$ strings.

% Uma árvore de sufixo generalizada para o conjunto $T$ indexa todas as \textit{strings} $S_i \in T$ em uma única árvore com as seguintes propriedades \cite{Gusfield1997}: (i) Cada nó interno, exceto a raiz, tem pelo menos 2 filhos; (ii) Cada aresta representa, por meio de seu rótulo, uma \textit{substring} de $S_i \in T$; (iii) Duas arestas que saiam do mesmo nó não podem representar \textit{substrings} com prefixo comum; e (iv) Para cada nó folha, rotulado com $k$ pares $[X_a, Y_b]$, a concatenação dos rótulos das arestas que estão no caminho da raiz até esse nó folha forma exatamente os sufixos $S_{X_a}[Y_b]$. 

A generalized suffix tree for the set $T$ indexes all the strings $S_i \in T$ in a single tree with the following properties \cite{Gusfield1997}:
(i) Each internal node, except the root, has at least two children. 
(ii) Each edge represents, by its label, a substring of $S_i \in T$. 
(iii) Two edges leaving from the same node cannot represent substrings with a common prefix. 
(iv) The path to a node (internal or leaf) $X$, denoted by $path(X)$, represents a substring formed by the concatenation of the labels on the path from the root to the node $X$.
(v) For each leaf node $L$, labeled with $k$ pairs $[X_a, Y_b]$, $path(L)$ is composed exactly by the suffixes $S_{X_a}[Y_b]$.

% \begin{enumerate}[(i)]
% \item Each internal node, except the root, has at least two children; 
% \item Each edge represents, by its label, a substring of $S_i \in T$; 
% \item Two edges leaving from the same node cannot represent substrings with a common prefix; 
% \item The path to a node (internal or leaf) $X$, denoted by $path(X)$, represents a substring formed by the concatenation of the labels on the path from the root to the node $X$.
% \item For each leaf node $L$, labeled with $k$ pairs $[X_a, Y_b]$, $path(L)$ is composed exactly by the suffixes $S_{X_a}[Y_b]$.
% \end{enumerate}


% A Figura \ref{fig:gst} ilustra uma árvore de sufixo generalizada para o conjunto $T = {S_1, S_2}$, onde $S_1 = \{abca\$\}$ e $S_1 = \{bcaba\$\}$.
% O nó folha destacado em cinza possui os pares $[1,4]$ e $[2,5]$, os quais representam os sufixos $S_1[4] = a\$$ e $S_2[5] = a\$$, respectivamente. 
% O caminho a um nó (interno ou folha) $X$, denotado por $path(X)$, representa uma \textit{substring} formada por meio da concatenação dos rótulos que estão no caminho do nó raiz ao nó $X$. 
% Por exemplo, o caminho ao nó $X$ na Figura~\ref{fig:gst} representa a \textit{substring} $bca$, isto é,  $path(X) = bca$. 

Figure \ref{fig:gst} shows an example of a generalized suffix tree for the set $T = \{S_1, S_2\}$, where $S_1 = abca\$$ and $S_2 = bcaba\$$.
The leaf node highlighted in gray has the pairs $[1,4]$ and $[2,5]$, which represent the suffixes $S_1[4] = a\$ $ and $S_2[5] = a\$$, respectively (property (v)).
The path to the node $X$ is equal to the substring $bca$ (property (iv)).

\begin{figure}[h]
\centering
\includegraphics[height=5.25cm]{figuras/gst}
\caption{Example of a generalized Suffix Tree}
\label{fig:gst}
\end{figure}

% O algoritmo trivial de construção de árvores de sufixo generalizada é realizado da seguinte forma. Inicialmente cria-se um nó raiz $R[T]$. Em seguida, para cada \textit{string} $S_i \in T$ adicionam-se todos os sufixos de $S_i$ na árvore. A cada iteração, conforme necessário, as arestas são divididas de forma a preservar a propriedades da árvore. A busca por uma \textit{substring} em uma árvore de sufixo generalizada é feita de forma determinística, a partir do nó raiz realiza-se o casamento entre a sequência de consulta e as \textit{substrings} na árvore. A complexidade de tempo é linear ao tamanho da \textit{substring} de consulta~\cite{Gusfield1997}.

The trivial algorithm for generalized suffix tree construction is described as follows.
Initially, it creates a root node $R[T]$. 
Then, for each string $S_i \in T$, it adds up all the suffixes of $S_i$ in the tree. %At each iteration, if necessary, the edges are divided in order to preserve the properties of the tree.
In order to preserve the properties of the tree, during each iteration, edges are divided if necessary.
Regarding the substring search in a generalized suffix tree, it is done deterministically.
Starting from the root node, it performs a substrings matching between the query string and the substrings in the tree.
The search time complexity is linear to the size of the substring query \cite{Gusfield1997}.
