Tomasz Kociumaka

collaborators

5 papers

cs.DS2025

Faster Algorithms for Longest Common Substring

Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski +1

In the classic longest common substring (LCS) problem, we are given two strings $S$ and $T$ , each of length at most $n$ , over an alphabet of size $I ¨ $ , and we are asked to find a l…

cs.DS2025

Space-Efficient k-Mismatch Text Indexes

Tomasz Kociumaka, Jakub Radoszewski

A central task in string processing is text indexing, where the goal is to preprocess a text (a string of length $n$ ) into an efficient index (a data structure) supporting queries…

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…

cs.DS2024

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz

Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text $T$ of length $n$ , a pattern $P$ of length $m$ , and a threshold $k$ , the task is to…

cs.DS2024

On the Communication Complexity of Approximate Pattern Matching

Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz

The decades-old Pattern Matching with Edits problem, given a length- $n$ string $T$ (the text), a length- $m$ string $P$ (the pattern), and a positive integer $k$ (the threshold), as…