## 3 Off-Line Compression by Longest-First Substitution
### How to Update \(\mathit{SLSTree}(w_{k}^{i-1})\) to \(\mathit{SLSTree}(w_{k}^{i})\)
**Lemma 8**: _For each \(t\), we can locate node \(s\) such that \(\mathit{str}(s)=w_{k}^{i}[p-t:p-1]\) in amortized constant time._  
_Proof._ Let \(x_{p-t}\) be the longest node in the tree such that \(\mathit{str}(x_{p-t})\) is a prefix of \(w_{k}^{i}[p-t:p-1]\). Figure 4: Illustration of Case 1 of Lemma 7. Figure 3: \(\mathit{LRF}(w_{k})\) at position \(p\) of \(w_{k}^{i-1}\) is replaced by non-terminal symbol \(A_{k}\) in \(w_{k}^{i}\). Every \(w_{k}^{i-1}[p-t:]\) is removed from the tree and every \(w_{k}^{i}[p-t:]\) is inserted into the tree (the light-shaded suffixes in the right figure). In addition, every \(w_{k}^{i-1}[p+h:]\) for \(1\leq h\leq|\mathit{LRF}(w_{k})|-1\) is removed from the tree (the dark-shaded suffixes in the right figure). Consider the largest possible \(t\) and denote it by \(t_{\max}\). Since \(t_{\max}\leq|\mathit{LRF}(w_{k})|\), the node \(x_{p-t_{\max}}\) can be found in \(O(|\mathit{LRF}(w_{k})|)\) time by going down the path that spells out \(w_{k}^{i}[p-t_{\max}:p-1]\) from the root node (recall that \(\Sigma\) is fixed). Let \(z\in\Sigma^{*}\) be the string such that \(\mathit{str}(x_{p-t_{\max}})z=w_{k}^{i}[p-t_{\max}:p-1]\). If \(z\
eq\varepsilon\), then we create a new child node \(s_{p-t_{\max}}\) of \(x_{p-t_{\max}}\) such that \(\mathit{str}(s_{p-t_{\max}})=w_{k}^{i}[p-t_{\max}:p-1]\). Otherwise, we set \(s_{p-t_{\max}}=x_{p-t_{\max}}\). Now assume that we have located nodes \(x_{p-t}\) and \(s_{p-t}\). We can then locate \(s_{p-t+1}\) as follows. Consider node \(x_{p-t+1}\). Remark that \(\mathit{str}(\mathit{suf}(x_{p-t}))\) is a prefix of \(\mathit{str}(x_{p-t+1})\), and thus we can detect \(x_{p-t+1}\) in \(O(|\mathit{str}(x_{p-t+1})|-|\mathit{str}(\mathit{suf}(x_{p-t}))|)\) time by using the suffix link. After finding \(x_{p-t+1}\), we can locate or create \(s_{p-t+1}\) in constant time. The total time cost for detecting \(x_{p-t}\) for all \(1\leq t\leq t_{\max}\) is linear in  
\[\sum_{t=2}^{t_{\max}}(|\mathit{str}(x_{p-t+1})|-|\mathit{str}( \mathit{suf}(x_{p-t}))|)\] \[= |\mathit{str}(x_{p-1})|-|\mathit{str}(\mathit{suf}(x_{p-2}))|\] \[+ |\mathit{str}(x_{p-2})|-|\mathit{str}(\mathit{suf}(x_{p-3}))|\] \[\ldots\ldots\] \[+ |\mathit{str}(x_{p-t_{\max}+1})|-|\mathit{str}(\mathit{suf}(x_{p- t_{\max}}))|\] \[= |\mathit{str}(x_{p-1})|-|\mathit{str}(\mathit{suf}(x_{p-t_{\max}} ))|+t_{\max}-2\] \[= |\mathit{str}(x_{p-1})|-|\mathit{str}(x_{p-t_{\max}})|+t_{\max}-1\] \[\leq t_{\max}\leq|\mathit{LRF}(w_{k})|.\]  
Hence we can locate each \(s_{p-t}\) in amortized constant time. Let \(v\) be the reference node in the path from the root to some \(\mathit{leaf}_{p-t}\). Assume that \(\mathit{leaf}_{p-t}\) is removed from the subtree of \(v\), and redirected to node \(s\) in the same path, such that \(\mathit{str}(s)=w_{k}^{i}[p-t:p-1]\). In order to update \(\mathit{SLSTree}(w_{k}^{i-1})\) to \(\mathit{SLSTree}(w_{k}^{i})\), we have to maintain triple \(\langle\min(v),\max(v),\card(v)\rangle\) for node \(v\). One may be concerned that if \(p-t\) is neither \(\min(v)\) or \(\max(v)\) and \(\card(v)\geq 4\) in  
Figure 3:0 Illustration of Case 2 of Lemma 7. _SLSTree\((w_{k}^{i-1})\)_, the occurrences of \(str(v)\) in \(\mathit{SLSTree}(w_{k}^{i})\) do not form a single arithmetic progression any more. However, we have the following lemma. For any factor \(y\) of \(w_{k}^{i}\), let \(\mathit{Dead}_{w_{k}^{i}}(y)=\mathit{BP}_{w_{k}^{i-1}}(y)\backslash\mathit{BP} _{w_{k}^{i}}(y)\), namely, \(\mathit{Dead}_{w_{k}^{i}}(y)\) denotes the occurrences of \(y\) in \(w_{k}^{i-1}\) that overlap with the \(i\)-th greedily selected occurrence of \(\mathit{LRF}(w_{k})\) in \(w_{k}\). **Lemma 9**: _Let \(v\) be any reference node of \(\mathit{SLSTree}(w_{k}^{i})\) such that \(\#\mathit{occ}_{w_{k}^{i}}(\mathit{str}(v))=1\). For any integer \(m,n\), if \(m,n\in\mathit{BP}_{w_{k}^{i}}(\mathit{str}(v))\), then there is no integer \(r\) such that \(m<r<n\) and \(r\in\mathit{Dead}_{w_{k}^{i}}(\mathit{str}(v))\). (See Figure 6)._  
Proof.