# Sliding Suffix Tree
## 2 Notation and Preliminaries
### [PERSON]'s Online Suffix Tree Construction Algorithm  
In Reference [17], [PERSON] presented an incremental suffix tree construction algorithm which builds the data structure in a single pass. During the construction, the algorithm maintains the following invariants in amortized constant time:  
* Implicit buffer \(B\), which corresponds to the longest repeated _suffix_ of the text processed so far,
* the _active node_\(\beta\), which represents a node where we end up by navigating \(B\) in the suffix tree constructed so far, i.e., \(B\) is a prefix of a string spelled out by \(\beta\).  
Figure 1: Illustration of the suffix tree for text ABRACADABRAS including the implicit labels. Suffix links connecting internal nodes are drawn as dotted green lines. Values in each internal node represent the start index and the length of a label on the incoming edge, whereas the value of a leaf represent the suffix position in the text.  
The execution of the algorithm can be viewed as an automaton which reads a character \(c\) from the input stream. The automaton starts and remains in the _buffering state_ while \(c\) matches the next character of the incoming edge's label of \(\beta\). If the end of the label is reached (i.e., \(|B|=|\beta|\)), a child in the direction of \(c\) is taken, and this child becomes a new active node \(\beta\). Finally, \(c\) is (implicitly) appended to \(B\).  
On the other hand, if \(B\) cannot be extended by \(c\) in a tree, the automaton enters the _expanding state_. First, it inserts a new branch in the direction of \(c\), with a single leaf storing the suffix position \(n-|B|+1\). If \(|B|=|\beta|\), the new branch is added as a child to \(\beta\). Otherwise, if \(|B|<|\beta|\), the incoming edge of \(\beta\) is split, such that the string depth of the newly inserted internal node is \(|B|\), and the new branch is added to this node. Once the branch is inserted, the first character is removed from \(B\), obtaining new \(B^{\prime}=B[2:]\). A new active node corresponding to \(B^{\prime}\) is found in the following way. Let \(\alpha\) denote the parent of the original active node \(\beta\). Then the new active node \(\beta^{\prime}\) is a node obtained by navigating suffix \(B^{\prime}[|\alpha|:]\) from a node suffix\(\_\)link(\(\alpha\)). When \(\beta^{\prime}\) is obtained, \(c\) is reconsidered. If a branch in the direction of \(c\) exists, the automaton switches back to buffering state. Otherwise, it remains in the expanding state and repeats the new branch insertion. Each time the expanding state is re-entered, \(B\) is shortened by one character. In the worst case, if \(c\) does not occur yet in the text, the suffix links will be followed all the way up to the root node, and \(c\) will be added as a new child to the root node. In this case, the implicit buffer \(B\) will be an empty string.  
To wrap up, the currently constructed suffix tree is _un-finalized_, until \(B\) is completely emptied. Moreover, there are exactly \(|B|\) leaves missing in the un-finalized tree, and they correspond to suffixes of \(B\). For finite texts, we finalize the suffix tree at the end by appending a unique character \(\$\), which forces the algorithm to empty \(B\) and finalize the tree. For infinite streams, however, there is no final character. Consequently, we need to support:  
1. Queries: When performing a query, we need to report the occurrences, both in the partially constructed suffix tree and in \(B\).
2. Maintenance: The original [PERSON]'s algorithm supports adding a new character to the indexed text. When a window is shifted, we also remove the oldest (longest) suffix from the text.