52 citations · 133 across the 25 of their papers we have counts for
6 papers · 1 filter
Faster two-dimensional pattern matching with mismatches
Jonas Ellert, Paweł Gawrychowski, Adam Górkiewicz +1
The classical pattern matching asks for locating all occurrences of one string, called the pattern, in another, called the text, where a string is simply a sequence of characters.…
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…
Regular Languages in the Sliding Window Model
Moses Ganardi, Danny Hucke, Markus Lohrey +2
We study the space complexity of the following problem: For a fixed regular language , we receive a stream of symbols and want to test membership of a sliding window of size …
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…