7 papers
Metric Weighted Edit Distance: -Approximation in Time
Debarati Das, Evangelos Kipouridis, Tomasz Kociumaka
For every , we give a randomized -approximation to weighted edit distance when the costs form a metric on the alphabet augmented with a gap…
The Communication Complexity of Pattern Matching with Edits Revisited
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
In the decades-old Pattern Matching with Edits problem, given a length- string (the text), a length- string (the pattern), and a positive integer (the threshold),…
Time-Optimal Construction of String Synchronizing Sets
Jonas Ellert, Tomasz Kociumaka
A key principle in string processing is local consistency: using short contexts to handle matching fragments of a string consistently. String synchronizing sets [Kempa, Kociumaka;…
Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
Anouk Duyster, Tomasz Kociumaka
A Random Access query to a string asks for the character at a given position . In bits of space, this fundamental task admits consta…
Pattern Matching under Weighted Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
In Pattern Matching with Weighted Edits (PMWED), we are given a pattern of length , a text of length , a positive threshold , and oracle access to a weight functio…
Near-Optimal Property Testers for Pattern Matching
Ce Jin, Tomasz Kociumaka
The classic exact pattern matching problem, given two strings -- a pattern of length and a text of length -- asks whether occurs as a substring of . A proper…
Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
Anouk Duyster, Tomasz Kociumaka
Internal Pattern Matching (IPM) queries on a text , given two fragments and of such that , ask to compute all exact occurrences of within . IPM quer…