39 citations · 241 across the 54 of their papers we have counts for
9 papers · 1 filter
Towards a Definitive Compressibility Measure for Repetitive Sequences
Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza
Unlike in statistical compression, where Shannon's entropy is a definitive lower bound, no such clear measure exists for the compressibility of repetitive sequences. Since statisti…
Internal Dictionary Matching
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed +3
We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary in fragments of a given string of length . The di…
Weighted Shortest Common Supersequence Problem Revisited
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis +5
A weighted string, also known as a position weight matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSC…
Circular Pattern Matching with Mismatches
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis +5
The -mismatch problem consists in computing the Hamming distance between a pattern of length and every length- substring of a text of length , if this distance…
On Longest Common Property Preserved Substring Queries
Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga +3
We revisit the problem of longest common property preserving substring queries introduced by~Ayad et al. (SPIRE 2018, arXiv 2018). We consider a generalized and unified on-line set…
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa, Tomasz Kociumaka
Burrows-Wheeler transform (BWT) is an invertible text transformation that, given a text of length , permutes its symbols according to the lexicographic order of suffixes of…
RLE edit distance in near optimal time
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2
We show that the edit distance between two run-length encoded strings of compressed lengths and respectively, can be computed in time. This improv…
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
Katrin Casel, Joel D. Day, Pamela Fleischmann +3
We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two importa…
Quasi-Linear-Time Algorithm for Longest Common Circular Factor
Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos +6
We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings and of length , we are to compute the longest factor of whose cyclic shift occ…