# Sliding Suffix Tree
## 3 Sliding Suffix Tree
### Queries  
To find all occurrences of query \(Q\) in \(W\), we first navigate \(Q\) in \(\mathcal{T}\). Let \(\mathcal{T}_{Q}\) correspond to a subtree rooted at the node where we finished the navigation. Leaves of \(\mathcal{T}_{Q}\) make up the first part of the resulting set. In Figure 2, \(occ_{1}\) corresponds to this type of occurrence. Also, the position of \(occ_{2}\) in the same figure will be contained in one of the leaves of \(\mathcal{T}_{Q}\), since \(\mathcal{T}\) contains all suffixes that _start_ at the beginning of \(W\), up to the beginning of \(B\). The second part of the resulting set are the missing leaves of \(\mathcal{T}_{Q}\) due to the un-finalized state of \(\mathcal{T}\). More formally, we want to find the missing leaves which correspond to suffixes of \(B\) beginning with \(Q\). \(occ_{3}\) in Figure 2 illustrates one such position. We consider three cases:  
Case 1: \(|B|<|Q|\)  
Obviously, there are no matches of \(Q\) in \(B\), and we solely return the leaves of \(\mathcal{T}_{Q}\). Case 2: \(|B|=|Q|\)  
We check whether the active node \(\beta\) is the root node of \(\mathcal{T}_{Q}\). If this is true, then \(B\) equals \(Q\), and we add position \(n-|B|+1\) to the resulting set. Case 3: \(|B|>|Q|\)  
First, we claim that the navigated subtree \(\mathcal{T}_{Q}\) always exists, if there are any occurrences of \(Q\) to be found in \(B\). Lemma 1: _If \(Q\) exists in buffer \(B\), then a subtree \(\mathcal{T}_{Q}\) exists by navigating the query \(Q\) in \(\mathcal{T}\)._  
Proof: If \(Q\) exists somewhere in \(B\), then \(Q\) is a substring of the string spelled out by \(\beta\). From the property of the suffix tree, by following the suffix links from \(\beta\) we will find a root of \(\mathcal{T}_{Q}\) which spells out a string starting with \(Q\). In this case, we find all occurrences of \(Q\) in two steps:  
**Step 1: Map positions of \(Q\) from \(\mathcal{T}_{Q}\) to \(B\)**  
We consider the relation of each leaf in \(\mathcal{T}_{Q}\) to \(\beta\). Take \(leaf(\beta)\) and let this leaf store some position \(x\). Then, for each leaf in a subtree rooted at \(\mathcal{T}_{Q}\), let \(i\) correspond to the position stored in a leaf. If \(x\leq i\leq x+|B|-|Q|\), then \(Q\) also occurs at position \(n-|B|+(i-x)+1\). We add this position to the resulting set. By the definition of \(leaf\), \(x\) corresponds to the position stored in _any_ descendant leaf of \(\beta\). It's fine if \(x\leq n-2|B|\), as the leaves of \(\mathcal{T}_{Q}\) store a superset of positions relative to all leaves of \(\beta\), due to the condition \(|\beta|\geq|\mathcal{T}_{Q}|\). Therefore, taking any descendant leaf of \(\beta\) suffices to compute _all  
Figure 2: On the left: Illustration of partially constructed suffix tree \(\mathcal{T}\) with implicit buffer \(B\) and active node \(\beta\). On the right: Illustration of the stream, the sliding window \(W\), the implicit buffer \(B\), and three cases for positions of the query strings \(occ_{1}\), \(occ_{2}\), and \(occ_{3}\). occurrences of \(Q\) in \(B\) once we visit all leaves of \(\mathcal{T}_{Q}\). However, if \(x>n-2|B|\), we need to proceed to Step 2. **Step 2: Find all repeated occurrences of \(Q\) in \(B\)**  
Additional occurrences of \(Q\) may exist in \(B\) if \(x>n-2|B|\), because the suffix tree (and consequently \(\mathcal{T}_{Q}\)) is finalized only up to position \(n-|B|\). Observe in Figure 3a that the string \(B\) starting at \(x\) overlaps the string \(B\) starting at \(n-|B|+1\). Because two equal strings overlap, the first string determines the beginning of the second one and, consequently, also the beginning of the first one. This overlapping yields a repetitive pattern inside \(B\), and if \(Q\) occurs in the beginning of \(B\) then it will also occur at each subsequent repetition of this pattern. The following lemma formally defines the repetitive pattern \(P\) and Figure 3b illustrates the occurrences of \(P\) in \(B\). Lemma 2 (The Buffer Pumping Lemma): _Let \(leaf(\beta)\) store the position \(x\), such that \(x>n-2|B|\).