## 3 Non-Overlapping LZSS
### Complexity Bounds

Table 1: Complexities for answering an LZ78 substring compression query with different suffix tree representations. The query is on an interval \(\mathcal{I}\subset[1\ldots n]\). A query additionally needs an array of \(z_{78[\mathcal{I}]}\lg n=\mathcal{O}(n\lg\sigma)\) bits of space as described in Section 4.7. If there are characters of the alphabet appearing nowhere in the text, we additionally need to keep the text available during a query, which adds \(n\lg\sigma\) bits to the query space complexity of the SST solution. \begin{table}
\begin{tabular}{l l l} \hline \hline
**Data Structure \(\mathcal{D}\)** & **Operation Time \(t_{\mathcal{D}}\)** & **Space \(s_{\mathcal{D}}\) in Bits** \\ \hline plain array & \(\mathcal{O}(1)\) & \(n\lg|\mathcal{I}|\) \\ [PERSON] et al. [50] & \(\mathcal{O}(\lg z/\lg\lg z)\) amortized & \(z\lg(n|\mathcal{I}|)+o(z)\) \\ backyard Cuckoo hashing [51] & \(\mathcal{O}(\lg(1/\epsilon)/\epsilon^{2})\) expected & \((1+\epsilon)z\lg(n|\mathcal{I}|)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Dynamic dictionary representations usable in our cpST approach (cf. Section 4.8) for \(\mathcal{D}\) mapping a light node represented in \(\lg n\) bits to the lowest edge witness within its heavy path represented in \(\lg|\mathcal{I}|\) bits. \(z\coloneqq z_{78[\mathcal{I}]}\) denotes the number of LZ78 factors of \(T[\mathcal{I}]\), which is an upper bound on the number of edge witnesses. An operation is a lookup or an insertion. We are interested in instances with \(t_{\mathcal{D}}=o(\lg z)\) (since, otherwise, the approach of Section 4.5 is favorable). \(\epsilon\in(0,1)\) is a selectable constant. ## Institutional Review Board Statement: Not applicable. **Informed Consent Statement:** Not applicable. **Data Availability Statement:** Not applicable. **Acknowledgments:** We thank [PERSON] for helpful comments on the part of the non-overlapping LZSS factorization (Section 3) as part of the thesis ([53] [Section 3.6.1]). We thank the anonymous reviewers for their insightful remarks on improving the quality of this article. A reviewer discovered that Type 3 factors had been neglected in the analysis of the time complexity analysis of the LPnF computation in an early version of the manuscript. **Conflicts of Interest:** The author declares no conflict of interest. ## References

* (1) [PERSON]; [PERSON] A universal algorithm for sequential data compression. _IEEE Trans. Inf. Theory_**1977**, _23_, 337-343. [CrossRef]
* (2) [PERSON]; [PERSON] Compression of individual sequences via variable-rate coding. _IEEE Trans. Inf. Theory_**1978**, _24_, 530-536. [CrossRef]
* (3) [PERSON]; [PERSON] Data compression via textural substitution. _J. ACM_**1982**, _29_, 928-951. [CrossRef]
* (4) [PERSON]; [PERSON] [PERSON]; [PERSON]; [PERSON] [PERSON] Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees. _Algorithmica_**2018**, _80_, 2048-2081. [CrossRef]
* (5) [PERSON]; [PERSON] Computing Longest Previous non-overlapping Factors. _Inf. Process. Lett._**2011**, _111_, 291-295. [CrossRef]
* (6) [PERSON]; [PERSON] Substring compression problems. In Proceedings of the SODA, Vancouver, BC, Canada, 23-25 January 2005; pp. 321-330. * (7) [PERSON] Space-efficient Static Trees and Graphs. In Proceedings of the FOCS, Research Triangle Park, NC, USA, 30 October-1 November 1989; pp. 549-554. * (8) [PERSON] Compact Pat Trees. Ph.D. Thesis, University of Waterloo, Waterloo, ON, Canada, 1996. * (9) [PERSON]; [PERSON] Suffix Arrays: A New Method for On-Line String Searches. _SIAM J. Comput._**1993**, _22_, 935-948. * (10) [PERSON] Compressed Suffix Trees with Full Functionality. _Theory Comput. Syst._**2007**, _41_, 589-607. [CrossRef]
* (11) [PERSON]; [PERSON] Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. _SIAM J. Comput._**2005**, _35_, 378-407. * (12) [PERSON]; [PERSON]; [PERSON] Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. _SIAM J. Comput._**2009**, _38_, 2162-2178.