Word Break on SLP-Compressed Texts

Word Break is a prototypical factorization problem in string processing: Given a word w of length N and a dictionary D = {d1, d2,... , dK} of K strings, determine whether we can partition w into words from 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 O(g·m + M) time, where m = maxK i=1 |di |, M = PK i=1 |di |, and = 2 is the matrix multiplication exponent. We obtain our algorithm as a simple corollary of a more general result: We show that in O(gm + M) time, we can index the input text w so that solving the Word Break problem for any of its substrings takes O(m2 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 O(g·m2-ϵ + M) time for any ϵ > 0.