## 3 Off-Line Compression by Longest-First Substitution
### How to Find \(Lrf(w_{k})\) Using \(\mathit{SLSTree}(w_{k})\)  
In this section, we show how to find an LRF of \(w_{k}\) from \(\mathit{SLSTree}(w_{k})\). The next lemmas characterize an LRF of \(w_{k}\) that is _not_ represented by a node of \(\mathit{SLSTree}(w_{k})\). **Lemma 1**: _If an LRF \(x\) of \(w_{k}\) is not represented by a node of \(\mathit{SLSTree}(w_{k})\), then \(\max\mathit{BP}_{w_{k}}(x)=\min\mathit{BP}_{w_{k}}(x)+|x|\)._  
_Proof._ Let \(i=\min\mathit{BP}_{w_{k}}(x)\) and \(j=\max\mathit{BP}_{w_{k}}(x)\). Since \(x\) is a repeating factor of \(w_{k}\), \(|\mathit{BP}_{w_{k}}(x)|\geq 2\), which means that \(i\
eq j\). If \(w_{k}[i+|x|]\
eq w_{k}[j+|x|]\), then it contradicts the precondition that \(x\) is not represented by a node of \(\mathit{SLSTree}(w_{k})\). Hence we have \(w_{k}[i+|x|]=w_{k}[j+|x|]\). Moreover, since \(x\) is an LRF of \(w_{k}\), we have \(j\geq i+|x|\). However, if we assume \(j>i+|x|\), this contradicts the precondition that \(x\) is an LRF of \(w_{k}\), since \(w_{k}[i+|x|]=w_{k}[j+|x|]\) and we obtain a longer LRF \(w_{k}[i:i+|x|]=w_{k}[j:j+|x|]\). Hence we have \(j=i+|x|\). \(\Box\)  
The above lemma implies that an LRF \(x\) is not represented by a node of \(\mathit{SLSTree}(w_{k})\) only if the first and the last occurrences of \(x\) form a _square_\(xx\) in \(w_{k}\). For example, see Figure 1 that illustrates \(\mathit{SLSTree}(w_{0})\) for \(w=\mathtt{ababa\lx@paragraphsign}\). One can see that ab is an LRF of \(w_{0}\) but it is not represented by a node of \(\mathit{SLSTree}(w_{0})\). However, the following lemma guarantees that it is indeed sufficient to consider the strings represented by nodes of \(\mathit{SLSTree}(w_{k})\) as candidates for \(LRF(w_{k})\). **Lemma 2**: _Let \(x\) be an LRF of \(w_{k}\) that is not represented by a node of \(\mathit{SLSTree}(w_{k})\). Then, there exists another LRF \(y\) of \(w_{k}\) that is represented by a node of \(\mathit{SLSTree}(w_{k})\) such that \(|x|=|y|\). Moreover, \(x\) is no longer present in \(w_{k+1}\) after a substitution for \(y\) (see also Figure 2)._  
_Proof._ Let \(i=\min\mathit{BP}_{w_{k}}(x)\) and \(j=\max\mathit{BP}_{w_{k}}(x)\). It follows from Lemma 1 that \(j=i+|x|\). Suppose that \(x\) is represented on an edge from some node \(s\) to some node \(t\) of \(\mathit{STree}(w)\). Let \(u=\mathit{str}(t)\). Then we have \(\mathit{BP}_{w_{k}}(x)=\mathit{BP}_{w_{k}}(u)\). Let \(y\) be the suffix of \(u\) of length \(|x|\). It is clear that \(i+|u|-|y|,j+|u|-|y|\in\mathit{BP}_{w_{k}}(y)\). Since \(j=i+|x|=i+|y|\), \(\#\mathit{occ}_{w_{k}}(y)\geq 2\). Thus \(y\) is an LRF of \(w_{k}\). Since \(u\) is represented by node \(t\) and \(i=\min\mathit{BP}_{w_{k}}(u)\) and \(j=\max\mathit{BP}_{w_{k}}(u)\), we know that \(w_{k}[i+|u|]\
eq w_{k}[j+|u|]\). Hence \(y\) is represented by a node of \(\mathit{SLSTree}(w_{k})\). Since \(x\) occurs only within the region \(w_{k}[i:j+|u|-1]\), \(x\) does not occur in \(w_{k+1}\) after a substitution for \(y\). \(\Box\)  
In the running example of Figure 1, ba is an LRF of \(w_{0}\) that is represented by a node of \(\mathit{SLSTree}(w_{0})\). After its two occurrences are replaced by a non-terminal symbol \(A_{1}\), then \(\mathtt{ab}\), which is an LRF of \(w_{0}\) not represented by a node of \(\mathit{SLSTree}(w_{0})\), is no more present in \(w_{1}=\mathtt{a}A_{1}A_{1}\lx@paragraphsign\). After constructing \(\mathit{SLSTree}(w_{0})=\mathit{SLSTree}(w)\), we create a bin-sorted list of the internal nodes of \(\mathit{SLSTree}(w)\) in the decreasing order of their lengths. This can be done in linear time by a standardtraversal on \(\mathit{SLSTree}(w)\). We remark that a new internal node \(v\) may appear in \(\mathit{SLSTree}(w_{k})\) for some \(k\geq 1\), which did not exist in \(\mathit{SLSTree}(w_{k-1})\). However, we have that \(\mathit{len}(v)\leq|\mathit{LRF}(w_{k-1})|\). Thus, we can maintain the bin-sorted list by inserting node \(v\) in constant time.