Word Break on SLP-Compressed Texts
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916798501224448 |
|---|---|
| author | De, Rajat Kempa, Dominik |
| author_facet | De, Rajat Kempa, Dominik |
| contents | 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^ω + M)$ time, where $m = \max_{i=1}^{K} |d_i|$, $M = \sum_{i=1}^{K} |d_i|$, and $ω\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^ω + 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-ε} + M)$ time for any $ε> 0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23759 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Word Break on SLP-Compressed Texts De, Rajat Kempa, Dominik Data Structures and Algorithms 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^ω + M)$ time, where $m = \max_{i=1}^{K} |d_i|$, $M = \sum_{i=1}^{K} |d_i|$, and $ω\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^ω + 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-ε} + M)$ time for any $ε> 0$. |
| title | Word Break on SLP-Compressed Texts |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.23759 |