
Hardness of Detecting Abelian and Additive Square Factors in Strings
We prove 3SUMhardness (no strongly subquadratictime algorithm, assumin...
read it

Faster Algorithms for Longest Common Substring
In the classic longest common substring (LCS) problem, we are given two ...
read it

Internal Quasiperiod Queries
Internal pattern matching requires one to answer queries about factors o...
read it

Pattern Masking for Dictionary Matching
In the Pattern Masking for Dictionary Matching (PMDM) problem, we are gi...
read it

The Number of Repetitions in 2DStrings
The notions of periodicity and repetitions in strings, and hence these o...
read it

kApproximate Quasiperiodicity under Hamming and Edit Distance
Quasiperiodicity in strings was introduced almost 30 years ago as an ext...
read it

Counting Distinct Patterns in Internal Dictionary Matching
We consider the problem of preprocessing a text T of length n and a dict...
read it

Approximating longest common substring with k mismatches: Theory and practice
In the problem of the longest common substring with k mismatches we are ...
read it

Internal Dictionary Matching
We introduce data structures answering queries concerning the occurrence...
read it

Weighted Shortest Common Supersequence Problem Revisited
A weighted string, also known as a position weight matrix, is a sequence...
read it

Experimental Evaluation of Algorithms for Computing Quasiperiods
Quasiperiodicity is a generalization of periodicity that was introduced ...
read it

On the cyclic regularities of strings
Regularities in strings are often related to periods and covers, which h...
read it

Circular Pattern Matching with k Mismatches
The kmismatch problem consists in computing the Hamming distance betwee...
read it

QuasiLinearTime Algorithm for Longest Common Circular Factor
We introduce the Longest Common Circular Factor (LCCF) problem in which,...
read it

Efficient Representation and Counting of Antipower Factors in Words
A kantipower (for k > 2) is a concatenation of k pairwise distinct word...
read it

Efficient Computation of Sequence Mappability
Sequence mappability is an important task in genome resequencing. In th...
read it

Faster Recovery of Approximate Periods over Edit Distance
The approximate period recovery problem asks to compute all approximate ...
read it

Longest Common Factor Made Fully Dynamic
In the longest common factor (LCF) problem, we are given two strings S a...
read it

On Abelian Longest Common Factor with and without RLE
We consider the Abelian longest common factor problem in two scenarios: ...
read it

LinearTime Algorithm for Long LCF with k Mismatches
In the Longest Common Factor with k Mismatches (LCF_k) problem, we are g...
read it

String Periods in the OrderPreserving Model
The orderpreserving model (opmodel, in short) was introduced quite rec...
read it

On Periodicity Lemma for Partial Words
We investigate the function L(h,p,q), called here the threshold function...
read it

Longest common substring with approximately k mismatches
In the longest common substring problem we are given two strings of leng...
read it
Jakub Radoszewski
is this you? claim profile