39 citations · 255 across the 76 of their papers we have counts for
7 papers · 1 filter
Longest Gapped Repeats and Palindromes
Marius Dumitran, Paweł Gawrychowski, Florin Manea
A gapped repeat (respectively, palindrome) occurring in a word is a factor (respectively, ) of . In such a repeat (palindrome) is called the arm of the repe…
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…
Testing k-binomial equivalence
Dominik D. Freydenberger, Pawel Gawrychowski, Juhani Karhumäki +2
Two words and are said to be -binomial equivalent if every non-empty word of length at most over the alphabet of and appears as a scattered facto…
Efficiently Finding All Maximal -gapped Repeats
Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga +2
For , an -gapped repeat in a word is a factor of such that ; the two factors in such a repeat are called arms, while the factor is…
Sublinear-Space Distance Labeling using Hubs
Paweł Gawrychowski, Adrian Kosowski, Przemysław Uznański
A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded sole…
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…