research
∙
08/08/2023
Linear Time Construction of Cover Suffix Tree and Applications
The Cover Suffix Tree (CST) of a string T is the suffix tree of T with a...
share
research
∙
08/18/2022
Approximate Circular Pattern Matching
We consider approximate circular pattern matching (CPM, in short) under ...
research
∙
07/20/2021
Hardness of Detecting Abelian and Additive Square Factors in Strings
We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assumin...
research
∙
05/07/2021
Faster Algorithms for Longest Common Substring
In the classic longest common substring (LCS) problem, we are given two ...
research
∙
07/27/2020
Internal Quasiperiod Queries
Internal pattern matching requires one to answer queries about factors o...
research
∙
06/29/2020
Pattern Masking for Dictionary Matching
In the Pattern Masking for Dictionary Matching (PMDM) problem, we are gi...
research
∙
06/29/2020
The Number of Repetitions in 2D-Strings
The notions of periodicity and repetitions in strings, and hence these o...
research
∙
05/13/2020
k-Approximate Quasiperiodicity under Hamming and Edit Distance
Quasiperiodicity in strings was introduced almost 30 years ago as an ext...
research
∙
05/12/2020
Counting Distinct Patterns in Internal Dictionary Matching
We consider the problem of preprocessing a text T of length n and a dict...
research
∙
04/28/2020
Approximating longest common substring with k mismatches: Theory and practice
In the problem of the longest common substring with k mismatches we are ...
research
∙
09/25/2019
Internal Dictionary Matching
We introduce data structures answering queries concerning the occurrence...
research
∙
09/25/2019
Weighted Shortest Common Supersequence Problem Revisited
A weighted string, also known as a position weight matrix, is a sequence...
research
∙
09/25/2019
Experimental Evaluation of Algorithms for Computing Quasiperiods
Quasiperiodicity is a generalization of periodicity that was introduced ...
research
∙
08/05/2019
On the cyclic regularities of strings
Regularities in strings are often related to periods and covers, which h...
research
∙
07/03/2019
Circular Pattern Matching with k Mismatches
The k-mismatch problem consists in computing the Hamming distance betwee...
research
∙
01/31/2019
Quasi-Linear-Time Algorithm for Longest Common Circular Factor
We introduce the Longest Common Circular Factor (LCCF) problem in which,...
research
∙
12/19/2018
Efficient Representation and Counting of Antipower Factors in Words
A k-antipower (for k > 2) is a concatenation of k pairwise distinct word...
research
∙
07/31/2018
Efficient Computation of Sequence Mappability
Sequence mappability is an important task in genome re-sequencing. In th...
research
∙
07/27/2018
Faster Recovery of Approximate Periods over Edit Distance
The approximate period recovery problem asks to compute all approximate ...
research
∙
04/23/2018
Longest Common Factor Made Fully Dynamic
In the longest common factor (LCF) problem, we are given two strings S a...
research
∙
04/18/2018
On Abelian Longest Common Factor with and without RLE
We consider the Abelian longest common factor problem in two scenarios: ...
research
∙
02/18/2018
Linear-Time Algorithm for Long LCF with k Mismatches
In the Longest Common Factor with k Mismatches (LCF_k) problem, we are g...
research
∙
01/04/2018
String Periods in the Order-Preserving Model
The order-preserving model (op-model, in short) was introduced quite rec...
research
∙
01/03/2018
On Periodicity Lemma for Partial Words
We investigate the function L(h,p,q), called here the threshold function...
research
∙
12/22/2017