# Sliding Suffix Tree
## 3 Sliding Suffix Tree
### Maintenance  
The maintenance of the sliding suffix tree is based on the work by [PERSON] and [PERSON] [16; 18], with our addition of maintaining leaf shortcuts in internal nodes. Path Compression ([16], p. 26)  
During the expanding state of Ukkonen, we add to \(\mathcal{T}\) either one node (a new leaf is added to the active node) or two nodes (the incoming edge of the active node is split and a new leaf is added). When the expanding state is visited the first time, a new internal node \(\gamma^{\prime}\) is added to \(\mathcal{T}\). In the next step, either an expanding state is re-entered or a buffering state is entered. If the expanding state is re-entered, we repeat the procedure, obtaining a new node \(\gamma\) and a suffix link from \(\gamma^{\prime}\) to \(\gamma\). If the buffering state is entered, either a root node or a node containing the matched character is reached. Instead of creating a new node in \(\mathcal{T}\) as we did in the expanding state, we only add a suffix link to an existing node in \(\mathcal{T}\). To remove the oldest stored suffix from \(\mathcal{T}\), we first find the corresponding leaf (e.g., by taking the next leaf from some queue storing all inserted leaves). If the leaf's parent has three or more children, the parent remains unchanged and we just remove the leaf from \(\mathcal{T}\). On the other hand, if the leaf's parent has exactly two children, we remove the leaf from \(\mathcal{T}\) and also its parent \(\gamma\) from \(\mathcal{T}\). To remove \(\gamma\), we merge its incoming edges and the remaining outgoing edges. **Lemma 3**. : _Let \(\gamma\) be a node with two children in \(\mathcal{T}\), where one child \(\omega\) is a leaf storing the position of the longest suffix \(n-|W|+1\). Then, \(\gamma\) is not a terminating node of any suffix link._  
Proof by contradiction. : Let a subtree \(\tau\) be the other child of \(\gamma\). Assume there is \(\gamma^{\prime}\), which has suffix link terminating at \(\gamma\). Because \(\gamma^{\prime}\) exists, it also has to have at least two children. However, since the subtree rooted at \(\gamma^{\prime}\) is the subtree rooted at \(\gamma\) and the latter has only children \(\omega\) and \(\tau\), \(\gamma^{\prime}\) has respective children \(\omega^{\prime}\) and \(\tau^{\prime}\). Observe that \(\omega\) spells out a string \(W\), and, consequently, because of the suffix link relationship \(\omega^{\prime}\) spells out a string \(cW\) for some character \(c\in\Sigma\). Furthermore, since \(W\) is the longest string in the window, \(cW\) cannot be suffix in \(W\), which contradicts the original assumption. To wrap up, there is no suffix link terminating at \(\gamma\). Avoiding Unwanted Suffix Removals and Keeping a Valid Insertion Point ([16], pp. 26-28)  
At the moment of the oldest suffix removal, the corresponding leaf can be an active node \(\beta\). If this is the case, then \(B\) appears at two positions in the window: At the very beginning as a prefix of the removed suffix and at the very end as a suffix of the window which has not been finalized yet. Recall that, by definition, \(B\) corresponds to the longest repeated suffix of the window. Consequently, if we shift the window for one position to the right, the new longest repeated suffix becomes \(B[2\cdot]\). By doing this, we also need to execute the expanding state of [PERSON]'s algorithm and add a leaf storing the position \(n-|B|+1\), corresponding to the original \(B\). We can combine the removal of the oldest leaf and the addition of the new one by simply updating the position stored in the oldest leaf from \(n-|W|+1\) to \(n-|B|+1\). Figure 4 illustrates this case. To find a new \(\beta\) and an edge corresponding to the updated \(B\), we simply follow the suffix link of the \(\beta\)'s parent and navigate the remainder of \(B\) from the obtained node. Keeping Edge Labels and Leaf Shortcuts Valid ([16], pp. 28-30)  
The final step of the maintenance is to update internal node labels and shortcuts to leaves ([16], pp. 28-30).