39 citations · 241 across the 54 of their papers we have counts for
10 papers · 1 filter
Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka, Saeed Seddighin
We study dynamic algorithms for the longest increasing subsequence (\textsf{LIS}) problem. A dynamic \textsf{LIS} algorithm maintains a sequence subject to operations of the follow…
Tight Bound for the Number of Distinct Palindromes in a Tree
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter +1
For an undirected tree with edges labelled by single letters, we consider its substrings, which are labels of the simple paths between pairs of nodes. We prove that there are $…
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
Tomasz Kociumaka, Barna Saha
In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance prob…
Improved Circular -Mismatch Sketches
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz +2
The shift distance between two strings and of the same length is defined as the minimum Hamming distance between and any rotation (cyclic s…
Counting Distinct Patterns in Internal Dictionary Matching
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed +5
We consider the problem of preprocessing a text of length and a dictionary in order to be able to efficiently answer queries , that is, gi…
Approximating longest common substring with mismatches: Theory and practice
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski +1
In the problem of the longest common substring with mismatches we are given two strings and must find the maximal length such that there is a length- substr…
Time-Space Tradeoffs for Finding a Long Common Substring
Stav Ben-Nun, Shay Golan, Tomasz Kociumaka +1
We consider the problem of finding, given two documents of total length , a longest string occurring as a substring of both documents. This problem, known as the Longest Common…
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz +1
We revisit the -mismatch problem in the streaming model on a pattern of length and a streaming text of length , both over a size- alphabet. The current state-of-the-ar…
Faster Approximate Pattern Matching: A Unified Approach
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
Approximate pattern matching is a natural and well-studied problem on strings: Given a text , a pattern , and a threshold , find (the starting positions of) all substrings…
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka +2
We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n, both over an alphabet of size , compute the Hamming distance between the…