research
∙
08/18/2022
Approximate Circular Pattern Matching
We consider approximate circular pattern matching (CPM, in short) under ...
share
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
∙
08/30/2020
Tight Bound for the Number of Distinct Palindromes in a Tree
For an undirected tree with n edges labelled by single letters, we consi...
research
∙
07/27/2020
Internal Quasiperiod Queries
Internal pattern matching requires one to answer queries about factors o...
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/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
∙
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
∙
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/27/2018
Faster Recovery of Approximate Periods over Edit Distance
The approximate period recovery problem asks to compute all approximate ...
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
