39 citations · 241 across the 54 of their papers we have counts for
5 papers · 1 filter
On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski +2
We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings is sought containing as a factor ever…
Optimal Dynamic Strings
Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka +2
In this paper we study the fundamental problem of maintaining a dynamic collection of strings under the following operations: concat - concatenates two strings, split - splits a st…
Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter
We give efficient algorithms for ranking Lyndon words of length over an alphabet of size . The rank of a Lyndon word is its position in the sequence of lexicographically ord…
Fast Computation of Abelian Runs
Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq +2
Given a word and a Parikh vector , an abelian run of period in is a maximal occurrence of a substring of having abelian period .…
Approximating LZ77 via Small-Space Multiple-Pattern Matching
Johannes Fischer, Travis Gagie, Paweł Gawrychowski +1
We generalize Karp-Rabin string matching to handle multiple patterns in time and space, where is the length of the text and is…