Word Break on SLP-Compressed Texts
Rajat De, Dominik Kempa · 2025
Word Break is a prototypical factorization problem in string processing: Given a word$w$of length$N$and a dictionary$\mathcal{D}=\{d_{1},\ d_{2},\ \ldots,\ d_{K}\}$of$K$strings, determine whether we can partition$w$into words from$\mathcal{D}$. We propose the first algorithm that solves the Word Break problem over the SLP-compressed input text$w$. Specifically, we show that, given the string$w$represented using an SLP of size$g$we can solve the Word Break problem in$\mathcal{O}(g\cdot m^{\omega}+M)$time, where$m=\max_{i=1}^{K}\vert d_{i}\vert M=\sum_{i=1}^{K}\vert d_{i}\vert$, and$\omega\geq 2$is the matrix multiplication exponent. We obtain our algorithm as a simple corollary of a more general result: We show that in$\mathcal{O}(g\cdot m^{\omega}+M)$time, we can index the input text$w$so that solving the Word Break problem for any of its substrings takes$\mathcal{O}(m^{2}\log N)$time (independent of the substring length). Our second contribution is a lower bound: We prove that, unless the Combinatorial$k$-Clique Conjecture fails, there is no combinatorial algorithm for Word Break on SLP-compressed strings running in$\mathcal{O}(g\cdot m^{2-\epsilon}+M)$time for any$\epsilon > 0$.