39 citations · 241 across the 54 of their papers we have counts for
7 papers · 1 filter
An Algorithmic Bridge Between Hamming and Levenshtein Distances
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer +1
The edit distance between strings classically assigns unit cost to every character insertion, deletion, and substitution, whereas the Hamming distance only allows substitutions. In…
-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3
Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…
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- text , a length- pattern , and a…
Near-Optimal Search Time in -Optimal Space, and Vice Versa
Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares
Two recent lower bounds on the compressibility of repetitive sequences, , have received much attention. It has been shown that a length- string over an alphabet of s…
Faster Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
We consider the approximate pattern matching problem under the edit distance. Given a text of length , a pattern of length , and a threshold , the task is to find…
Computing Longest (Common) Lyndon Subsequences
Hideo Bannai, Tomohiro I, Tomasz Kociumaka +2
Given a string with length whose characters are drawn from an ordered alphabet of size , its longest Lyndon subsequence is a longest subsequence of that is a Lyndon…
Dynamic Suffix Array with Polylogarithmic Queries and Updates
Dominik Kempa, Tomasz Kociumaka
The suffix array of a text of length is a permutation of describing the lexicographical ordering of suffixes of , and it is considered to be…