Tomasz Walen

collaborators

3 papers

cs.DS2025

Fast Computation of $k$ -Runs, Parameterized Squares, and Other Generalised Squares

Yuto Nakashima, Jakub Radoszewski, Tomasz WaleÅ

A $k$ -mismatch square is a string of the form $X Y$ where $X$ and $Y$ are two equal-length strings that have at most $k$ 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 $n$ over an alphabet of size $I ¨ $ can be computed in $O (n / lo g_{I ¨} n)$ time in the word-RAM model. This paper…

cs.DS2025

Approximate Circular Pattern Matching

Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski +4

We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length- $n$ text $T$ , a length- $m$ pattern $P$ , and a…

Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares

Counting Distinct Square Substrings in Sublinear Time

Approximate Circular Pattern Matching

Fast Computation of $k$ -Runs, Parameterized Squares, and Other Generalised Squares