4 papers · 1 filter
Small Space Encoding and Recognition of -Palindromic Prefixes
Gabriel Bathie, Jonas Ellert, Tatiana Starikovskaya
Palindromes are non-empty strings that read the same forward and backward. The problem of recognizing strings that can be represented as the concatenation of even-length palindrome…
Longest Common Extensions with Wildcards: Trade-off and Applications
Gabriel Bathie, Itai Boneh, Panagiotis Charalampopoulos +2
We study the Longest Common Extension (LCE) problem in a string containing wildcards. Wildcards (also called "don't cares" or "holes") are special characters that match any other c…
Internal Pattern Matching in Small Space and Applications
Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya
In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our mai…
Pattern Matching with Mismatches and Wildcards
Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya
In this work, we address the problem of approximate pattern matching with wildcards. Given a pattern of length containing wildcards, a text of length , and an in…