On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
For researchers in string algorithms, this work provides improved tradeoffs for palindrome detection in texts with wildcards, though the improvements are incremental.
This paper presents the first non-trivial linear-space algorithm for computing all maximal palindromes in texts with wildcards, improving the best known time-memory product in certain parameter ranges. It also generalizes the methods to the k-mismatches setting.
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.