research
∙
08/07/2023
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
In the last decades, the necessity to process massive amounts of textual...
share
research
∙
07/14/2023
Approximating Edit Distance in the Fully Dynamic Model
The edit distance is a fundamental measure of sequence similarity, defin...
research
∙
05/11/2023
Optimal Algorithms for Bounded Weighted Edit Distance
The edit distance of two strings is the minimum number of insertions, de...
research
∙
02/08/2023
Weighted Edit Distance Computation: Strings, Trees and Dyck
Given two strings of length n over alphabet Σ, and an upper bound k on t...
research
∙
11/22/2022
An Algorithmic Bridge Between Hamming and Levenshtein Distances
The edit distance between strings classically assigns unit cost to every...
research
∙
11/14/2022
Bellman-Ford is optimal for shortest hop-bounded paths
This paper is about the problem of finding a shortest s-t path using at ...
research
∙
09/15/2022
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance
Computing the edit distance of two strings is one of the most basic prob...
research
∙
08/18/2022
Approximate Circular Pattern Matching
We consider approximate circular pattern matching (CPM, in short) under ...
research
∙
06/01/2022
Near-Optimal Search Time in δ-Optimal Space
Two recent lower bounds on the compressiblity of repetitive sequences, δ...
research
∙
04/06/2022
Faster Pattern Matching under Edit Distance
We consider the approximate pattern matching problem under the edit dist...
research
∙
01/18/2022
Computing Longest (Common) Lyndon Subsequences
Given a string T with length n whose characters are drawn from an ordere...
research
∙
01/04/2022
Dynamic Suffix Array with Polylogarithmic Queries and Updates
The suffix array SA[1..n] of a text T of length n is a permutation of {1...
research
∙
12/10/2021
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
The Dyck language, which consists of well-balanced sequences of parenthe...
research
∙
12/10/2021
How Compression and Approximation Affect Efficiency in String Distance Measures
Real-world data often comes in compressed form. Analyzing compressed dat...
research
∙
11/24/2021
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
We study the problem of approximating edit distance in sublinear time. T...
research
∙
11/03/2021
An Improved Algorithm for The k-Dyck Edit Distance Problem
A Dyck sequence is a sequence of opening and closing parentheses (of var...
research
∙
06/24/2021
Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays
The suffix array, describing the lexicographic order of suffixes of a gi...
research
∙
06/10/2021
Small space and streaming pattern matching with k edits
In this work, we revisit the fundamental and well-studied problem of app...
research
∙
05/13/2021
The Dynamic k-Mismatch Problem
The text-to-pattern Hamming distances problem asks to compute the Hammin...
research
∙
05/07/2021
Faster Algorithms for Longest Common Substring
In the classic longest common substring (LCS) problem, we are given two ...
research
∙
11/21/2020
Improved Dynamic Algorithms for Longest Increasing Subsequence
We study dynamic algorithms for the longest increasing subsequence (LIS)...
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/24/2020
Sublinear-Time Algorithms for Computing Embedding Gap Edit Distance
In this paper, we design new sublinear-time algorithms for solving the g...
research
∙
06/24/2020
Improved Circular k-Mismatch Sketches
The shift distance 𝗌𝗁(S_1,S_2) between two strings S_1 and S_2 of the sa...
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
∙
04/27/2020
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
We revisit the k-mismatch problem in the streaming model on a pattern of...
research
∙
04/17/2020
Faster Approximate Pattern Matching: A Unified Approach
Approximate pattern matching is a natural and well-studied problem on st...
research
∙
03/04/2020
Time-Space Tradeoffs for Finding a Long Common Substring
We consider the problem of finding, given two documents of total length ...
research
∙
01/01/2020
Approximating Text-to-Pattern Hamming Distances
We revisit a fundamental problem in string matching: given a pattern of ...
research
∙
10/23/2019
Resolution of the Burrows-Wheeler Transform Conjecture
Burrows-Wheeler Transform (BWT) is an invertible text transformation tha...
research
∙
10/04/2019
Towards a Definitive Measure of Repetitiveness
Unlike in statistical compression, where Shannon's entropy is a definiti...
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
∙
06/13/2019
On Longest Common Property Preserved Substring Queries
We revisit the problem of longest common property preserving substring q...
research
∙
05/03/2019
RLE edit distance in near optimal time
We show that the edit distance between two run-length encoded strings of...
research
∙
04/08/2019
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Burrows-Wheeler transform (BWT) is an invertible text transformation tha...
research
∙
02/28/2019
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
We investigate the locality number, a recently introduced structural par...
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
∙
05/24/2018
Longest Unbordered Factor in Quasilinear Time
A border u of a word w is a proper factor of w occurring both as a prefi...
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