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.

We construct the Compressed Form array data structure (CF array) that supports the array interface while requiring$\mathcal{O}(n)$bits of space to store$n$integers from the range$\{1,2, \ldots$, poly$(n)\}$, under the smoothness condition that large integers are spaced proportionally to their values:$\forall i \neq j,\lfloor\log \min \{A[i], A[j]\}\rfloor \leq\lfloor\log\vert j-i\vert \rfloor$.

Palindromes are sequences of characters that read the same forward and backward and have fascinated computer scientists for centuries due to their unique properties. The exploration of palindromes sheds light on fundamental principles of pattern recognition, sequence alignment, and combinatorics, making them a crucial concept in theoretical and applied disciplines. We introduce a novel method for compressing palindromic structures in strings, establishing upper and lower bounds for their efficient representation. We do so by presenting a data structure capable of storing all maximal palindromes (Manacher array) in sublinear space with near-optimal access time. Our approach reduces the memory overhead of storing palindromes, offering a new avenue for optimizing compression algorithms in text processing applications.

The recovery problem is the problem whose input is a corrupted text T that was originally periodic, and where one wishes to recover its original period. The algorithm’s input is T without any information about either the period’s length or the period itself. An algorithm that solves this problem is called a recovery algorithm. In order to make recovery possible, there must be some assumption that not "too many" errors corrupted the initial periodic string. This is called the error bound. In previous recovery algorithms, it was shown that a given error bound of n/((2+ε)p) can lead to O(log_{1+ε} n) period candidates, that are guaranteed to include the original period, where p is the length of the original period (unknown by the algorithm) and ε > 0 is an arbitrary constant. This paper provides the first analysis of the relationship between the error bound and the number of candidates, as well as identification of the error parameters that still guarantee recovery. We improve the previously known upper error bound on the number of corruptions, n/((2+ε)p), that outputs O(log_{1+ε} n) period candidates. We show how to (1) remove ε from the bound, (2) relax the error bound to allow more errors while keeping the candidates set of size O(log n). It turns out that this relaxation on the previously known upper bound is quite challenging. To achieve this result we provide what, to our knowledge, is the first known non-trivial lower bound on the Hamming distance between two periodic strings. This proof leads to an error bound, that produces a family of period candidates of size 2log₃ n. We show that this result is tight and further provide a compact representation of the period candidates. We call this representation the canonic period seed. In addition to providing less restrictive error bounds that guarantee a smaller candidate set, we also provide a hierarchy of more restrictive upper error bounds that asymptotically reduces the size of the potential period candidate set.