research
∙
02/02/2023
Optimal Heaviest Induced Ancestors
We revisit the Heaviest Induced Ancestors (HIA) problem that was introdu...
share
research
∙
08/18/2022
Approximate Circular Pattern Matching
We consider approximate circular pattern matching (CPM, in short) under ...
research
∙
04/06/2022
Faster Pattern Matching under Edit Distance
We consider the approximate pattern matching problem under the edit dist...
research
∙
06/03/2021
Internal Shortest Absent Word Queries in Constant Time and Linear Space
Given a string T of length n over an alphabet Σ⊂{1,2,…,n^O(1)} of size σ...
research
∙
05/07/2021
Faster Algorithms for Longest Common Substring
In the classic longest common substring (LCS) problem, we are given two ...
research
∙
03/04/2021
An Almost Optimal Edit Distance Oracle
We consider the problem of preprocessing two strings S and T, of lengths...
research
∙
02/14/2021
Fault-Tolerant Distance Labeling for Planar Graphs
In fault-tolerant distance labeling we wish to assign short labels to th...
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
∙
06/03/2020
Dynamic Longest Common Substring in Polylogarithmic Time
The longest common substring problem consists in finding a longest strin...
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/17/2020
Faster Approximate Pattern Matching: A Unified Approach
Approximate pattern matching is a natural and well-studied problem on st...
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
∙
11/05/2018
Almost Optimal Distance Oracles for Planar Graphs
We present new tradeoffs between space and query-time for exact distance...
research
∙
07/31/2018
Efficient Computation of Sequence Mappability
Sequence mappability is an important task in genome re-sequencing. In th...
research
∙
07/16/2018
Exact Distance Oracles for Planar Graphs with Failing Vertices
We consider exact distance oracles for directed weighted planar graphs i...
research
∙
06/07/2018
Alignment-free sequence comparison using absent words
Sequence comparison is a prerequisite to virtually all comparative genom...
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
∙
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/13/2018
