On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911616687144960 |
|---|---|
| author | Amir, Amihood Butman, Ayelet Itzhaki, Michael Sokol, Dina |
| author_facet | Amir, Amihood Butman, Ayelet Itzhaki, Michael Sokol, Dina |
| contents | This paper addresses the problem of identifying palindromic factors in texts that include wildcards -- special characters that match all others. These symbols challenge many classical algorithms, as numerous combinatorial properties are not satisfied in their presence. We apply existing wildcard-LCE techniques to obtain a continuous time-memory tradeoff, and present the first non-trivial linear-space algorithm for computing all maximal palindromes with wildcards, improving the best known time-memory product in certain parameter ranges. Our main results are algorithms to find and approximate all maximal palindromes in a given text. We also generalize both methods to the $k$-mismatches setting, with or without wildcards. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21140 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches Amir, Amihood Butman, Ayelet Itzhaki, Michael Sokol, Dina Data Structures and Algorithms This paper addresses the problem of identifying palindromic factors in texts that include wildcards -- special characters that match all others. These symbols challenge many classical algorithms, as numerous combinatorial properties are not satisfied in their presence. We apply existing wildcard-LCE techniques to obtain a continuous time-memory tradeoff, and present the first non-trivial linear-space algorithm for computing all maximal palindromes with wildcards, improving the best known time-memory product in certain parameter ranges. Our main results are algorithms to find and approximate all maximal palindromes in a given text. We also generalize both methods to the $k$-mismatches setting, with or without wildcards. |
| title | On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.21140 |