Tomasz Walen

activity

20222025

collaborators

4 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 $σ$ can be computed in $O (n / lo g_{σ} n)$ 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 $k$ -Edit Circular Pattern Matching ( $k$ -Edit CPM) problem, we are given a length- $n$ text $T$ , a length- $m$ pattern $P$ , and a positive integer threshold $k$ , and we are to…

cs.DS2022

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 under Edit Distance

Approximate Circular Pattern Matching

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