## 3 Non-Overlapping LZSS
### Complexity Bounds
* Otherwise (\(d-1\) is smaller than this height difference), the node whose exploration counter we want to increment is within the heavy path, and is either the \(d\)th or \((d+1)\)th descendent of \(v\). In total, for \(z\coloneqq z_{78|\mathcal{I}|}\), we can improve the \(z\lg z\) factor in the time bounds to \(z\cdot\min(\lg z,t_{\mathcal{D}}+\lg\lg n)\), which is \(z\cdot\min(\lg z,\lg z/\lg\lg z+\lg\lg n)\) when implementing \(\mathcal{D}\) with the dynamic dictionary of [PERSON] et al. [50], costing \(s_{\mathcal{D}}=z\lg(nz)+o(z)\) bits of additional working space during a query. More formally:

Theorem 4.1: _Given a text \(T[1\ldots n]\) of length \(n\) whose characters are drawn from an alphabet with size \(\sigma=n^{\mathcal{O}(1)}\), we can compute a data structure on \(T\) in \(\mathcal{O}(n)\) time that computes, given an interval \(\mathcal{I}\subset[1\ldots n]\), the LZ78 factorization of \(T[\mathcal{I}]\) in_

* \(\mathcal{O}(z_{78|\mathcal{I}})(\log_{\sigma}n+\min(\lg z_{78|\mathcal{I}},t_ {\mathcal{D}}+\lg\lg n))\) _tine using_ \(\mathcal{O}(n\lg\sigma)+s_{\mathcal{D}}\) _bits of space, or_
* \(\mathcal{O}(e^{-1}z_{78|\mathcal{I}})\min(\lg z_{78|\mathcal{I}},t_{\mathcal{D} }+\lg\lg n))\) _time using_ \((1+\epsilon)n\lg n+s_{\mathcal{D}}+\mathcal{O}(n)\) _bits of space,_where \(z_{78[\mathcal{I}]}\) is the number of computed LZ78 factors, \(\epsilon\in(0,1]\) is a selectable constant, and \(t_{\mathcal{D}}\) and \(s_{\mathcal{D}}\) are the time and space complexities of a dynamic dictionary associating a \(\lg n\)-bit integer with a \(\lg|\mathcal{I}|\)-bit value (cf. Table 2). Similar to Theorem 2, we need the read-only text stored for queries if there is a character in the alphabet that does not appear in \(T\)._

## 5 Conclusions

We used techniques introduced by [PERSON] et al. [4], which work on the succinct suffix tree (SST) and the compressed suffix tree (CST), to tackle the non-overlapping LZSS factorization and the LZ78 substring compression query problem. One of the main techniques is the usage of level ancestor queries to traverse a root-to-leaf path. For computing the non-overlapping LZSS factorization, our idea was to merge these techniques with the algorithm of [PERSON] [31] working in root-to-leaf traversals. To answer an LZ78 substring compression query, we combined exponential search with the level ancestor queries and could accelerate this by first searching in the centroid path-decomposed suffix tree cpST whenever the factor lengths become large. We wonder whether we can improve the space bounds for solving the semi-dynamic fringe marked ancestor problem (addressed in Section 4), where updates are restricted to marking a node that is a child of an already marked node; hence, the marked nodes form a connected subgraph of the suffix tree sharing at least the root. Without the need of the \(\mathcal{O}(n)\) words for the marked ancestor data structure, it becomes interesting to devise algorithms computing the reversed LZSS factorization [52] (see ([53] [Chapter 3.6.2])) in low memory. \begin{table}
\begin{tabular}{l l l} \hline \hline  & \multicolumn{2}{c}{**Construction**} \\ \hline
**Data Structure** & **Time** & **Space in Bits** \\ \hline suffix tree [45] & \(\mathcal{O}(n)\) & \(\mathcal{O}(n\lg n)\) \\ SST [4] [Section 2.2.3] & \(\mathcal{O}(n\epsilon^{-1})\) & \(n\lg\sigma+(1+\epsilon)n\lg n+\mathcal{O}(n)\) \\ CST [4] [Section 2.2.2] & \(\mathcal{O}(n)\) & \(\mathcal{O}(n\lg\sigma)\) \\ \hline \multicolumn{3}{c}{**Query**} \\ \hline
**Data Structure** & **Time** & **Space in Bits** \\ \hline suffix tree [45] & \(\mathcal{O}(z_{78[\mathcal{I}]})\) & \(\mathcal{O}(n\lg n)\) \\ SST [4] [Section 2.2.3] & \(\mathcal{O}(z_{78[\mathcal{I}]}\lg z_{78[\mathcal{I}]}\epsilon^{-1})\) & \(((1+\epsilon)n+z_{78[\mathcal{I}]})\lg n+\mathcal{O}(n)\) \\ CST [4] [Section 2.2.2] & \(\mathcal{O}(z_{78[\mathcal{I}]}(\lg z_{78[\mathcal{I}]}+\log_{\sigma}n))\) & \(\mathcal{O}(n\lg\sigma)\) \\ \hline \hline \end{tabular}
\end{table}