## Appendix  
In this appendix we show that the algorithm of [PERSON] et al. [28] for LFS2 takes \(O(n^{2})\) time, where \(n\) is the length of the input string. Consider string  
\[w=w_{0}=z_{0}=\texttt{aaaaaaabbbbbaaabbbbbcaaaaaaaa}\texttt{\$}.\]  
The [PERSON] algorithm constructs a suffix tree of \(w\), constructs a bin-sorted list of internal nodes of the tree, and updates the tree in a similar way to our algorithm in Section 3.3.. However, a critical difference is that any node \(v\) of their tree structure does _not_ store an ordered triple \(\langle\min(v),\max(v),\card(v)\rangle\) such that \(\min(v)=\min\mathit{BP}_{w}(\mathit{str}(v))\), \(\max(v)=\max\mathit{BP}_{w}(\mathit{str}(v))\), and \(\card(v)=\big{|}\mathit{BP}_{w}(\mathit{str}(v))\big{|}\). See Figure 8 which illustrates the suffix tree of \(w\). A bin-sorted list of internal nodes of \(\mathit{STree}(w)\) in decreasing order of their length is as follows:  
\[9:\texttt{aaaaabbbbb}\] \[8:\texttt{aaabbbbb}\] \[7:\texttt{aabbbbbb,aaaaaaa}\] \[6:\texttt{abbbbb,aaaaaa}\] \[5:\texttt{bbbbb,aaaaa}\] \[4:\texttt{bbbbb,aaaa}\] \[3:\texttt{bbb,aaa}\] \[2:\texttt{bb,aa}\] \[1:\texttt{b,a}\]  
In [28], [PERSON] et al. do not mention how they find occurrences of each node in the sorted list. Since they do not have an ordered triple \(\langle\min(v),\max(v),\card(v)\rangle\) for each node \(v\), the best possible way is to traverse the subtree of \(v\) checking the leaves in the subtree. Now, for the first LRF-candidate aaaabbbbb, we get positions \(4\) and \(13\) and find out that \(\mathit{LRF}(w)=\mathit{LRF}(z_{0})=\texttt{aaaabbbb}\). Then we obtain  
\[9:\texttt{aaaaabbbbb}\]0  
where \(A\) is a new non-terminal symbol that replaces \(\mathit{LRF}(z_{0})=\texttt{aaaaabbbbb}\). Now see Figure 9 which illustrates a generalized sparse suffix tree for  
\[9:\texttt{aaaaabbbbb}\]1  
To find \(LRF(z_{1})\), we check the nodes in the list as follows. * Length 8. The generalized suffix tree has no node representing aaabbbbb, and hence it is not an LRF. * Length 7. Since node aaaaaaa exists in the generalized suffix tree, we traverse its subtree and find 2 occurrences \(23\) and \(24\) in \(z_{1}\). However, it is not an LRF of \(z_{1}\). The other candidate aabbbbb does not have a corresponding node in the tree, so it is not an LRF, either. * Length 6. Node aaaaa exists in the generalized suffix tree and we find 3 occurrences \(23\), \(24\) and \(25\) in \(z_{1}\) by traversing the tree, but it is not an LRF. The tree has no node corresponding to abbbbb, hence it is not an LRF. * Length 5. Node aaaaa exists in the generalized suffix tree and we find 4 occurrences \(23\), \(24\), \(25\) and \(26\) in \(z_{1}\) by traversing the tree, but it is not an LRF. There is no node in the tree corresponding to bbbbbb. * Length 4. Node aaaa exists in the generalized suffix tree and we find 5 occurrences \(23\), \(24\), \(25\), \(26\) and \(27\). Now \(23\) and \(27\) are non-overlapping occurrences of aaaa, and hence it is an LRF of \(z_{1}\). Focus on the above operations where we examined factors of lengths from 7 to 5. The total time cost to find the occurrences for the LRF-candidates of these lengths is proportional to \(2+3+4\), but _none of them is an LRF of \(z_{1}\)_ in the end. In general, for any input string of the form  
\[9:\texttt{aaaaabbbbb}\]2  
the time cost of the [PERSON] algorithm for finding \(\mathit{LRF}(z_{1})\) is proportional to  
\[9:\texttt{aaaaabbbbb}\]3  
Since \(k=O(|w|)=O(n)\), the [PERSON] algorithm takes \(O(n^{2})\) time. In his PhD thesis [33], [PERSON] modified the algorithm so that all the occurrences of each candidate factor in \(w\) are stored in each element of the bin-sorted list (Section 3.1.3, page 55, line 1). However, this clearly requires \(O(n^{2})\) space. Note that using a suffix array cannot immediately solve this, since the lexicographical ordering of the suffixes can change due to substitution of LRFs, and no efficient methods to edit suffix arrays for such a case are known.