Computing Maximal Repeating Subsequences in a String
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908773403066368 |
|---|---|
| author | Gong, Mingyang Liyanage, Adiesha Sopp, Braeden Zhu, Binhai |
| author_facet | Gong, Mingyang Liyanage, Adiesha Sopp, Braeden Zhu, Binhai |
| contents | In this paper we initiate the study of computing a maximal (not necessarily maximum) repeating pattern in a single input string, where the corresponding problems have been studied (e.g., a maximal common subsequence) only in two or more input strings by Hirota and Sakai starting 2019. Given an input string $S$ of length $n$, we can compute a maximal square subsequence of $S$ in $O(n\log n)$ time, greatly improving the $O(n^2)$ bound for computing the longest square subsequence of $S$. For a maximal $k$-repeating subsequence, our bound is $O(f(k)n\log n)$, where \(f(k)\) is a computable function such that $f(k) < k\cdot 4^k$. This greatly improves the $O(n^{2k-1})$ bound for computing a longest $k$-repeating subsequence of $S$, for $k\geq 3$. Both results hold for the constrained case, i.e., when the solution must contain a subsequence $X$ of $S$, though with higher running times. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_12200 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computing Maximal Repeating Subsequences in a String Gong, Mingyang Liyanage, Adiesha Sopp, Braeden Zhu, Binhai Data Structures and Algorithms Formal Languages and Automata Theory 68W01, 68W32 F.2.2 In this paper we initiate the study of computing a maximal (not necessarily maximum) repeating pattern in a single input string, where the corresponding problems have been studied (e.g., a maximal common subsequence) only in two or more input strings by Hirota and Sakai starting 2019. Given an input string $S$ of length $n$, we can compute a maximal square subsequence of $S$ in $O(n\log n)$ time, greatly improving the $O(n^2)$ bound for computing the longest square subsequence of $S$. For a maximal $k$-repeating subsequence, our bound is $O(f(k)n\log n)$, where \(f(k)\) is a computable function such that $f(k) < k\cdot 4^k$. This greatly improves the $O(n^{2k-1})$ bound for computing a longest $k$-repeating subsequence of $S$, for $k\geq 3$. Both results hold for the constrained case, i.e., when the solution must contain a subsequence $X$ of $S$, though with higher running times. |
| title | Computing Maximal Repeating Subsequences in a String |
| topic | Data Structures and Algorithms Formal Languages and Automata Theory 68W01, 68W32 F.2.2 |
| url | https://arxiv.org/abs/2601.12200 |