3 papers
cs.DS2025
Fast Computation of -Runs, Parameterized Squares, and Other Generalised Squares
Yuto Nakashima, Jakub Radoszewski, Tomasz Waleń
A -mismatch square is a string of the form where and are two equal-length strings that have at most mismatches. Kolpakov and Kucherov [Theor. Comput. Sci., 2003…
cs.DS2025
Counting Distinct Square Substrings in Sublinear Time
Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski +3
We show that the number of distinct squares in a packed string of length over an alphabet of size can be computed in time in the word-RAM model. This paper i…
cs.DS2024
Approximate Circular Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski +3
In the -Edit Circular Pattern Matching (-Edit CPM) problem, we are given a length- text , a length- pattern , and a positive integer threshold , and we are to…