Word Break on SLP-Compressed Texts

Abstract

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,\dots ,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^{\ddot{I}}‰+M)$ time, where $m={\max }_{i=1}^K|d_i|$, $M={\sum }_{i=1}^K|d_i|$, and $\ddot{I}‰\ge 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^{\ddot{I}}‰+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-\hat{I}\mu }+M)$ time for any $\hat{I}\mu >0$.

Accepted to DCC 2025