research
∙
11/30/2022
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
In Gapped String Indexing, the goal is to compactly represent a string S...
share
research
∙
09/02/2022
Elastic-Degenerate String Matching with 1 Error
An elastic-degenerate string is a sequence of n finite sets of strings o...
research
∙
08/18/2022
Approximate Circular Pattern Matching
We consider approximate circular pattern matching (CPM, in short) under ...
research
∙
07/03/2022
Symbolic Regression is NP-hard
Symbolic regression (SR) is the task of learning a model of data in the ...
research
∙
12/20/2021
String Sampling with Bidirectional String Anchors
The minimizers sampling mechanism is a popular mechanism for string samp...
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
∙
07/16/2020
Substring Complexity in Sublinear Space
Shannon's entropy is a definitive lower bound for statistical compressio...
research
∙
07/16/2020
String Sanitization Under Edit Distance: Improved and Generalized
Let W be a string of length n over an alphabet Σ, k be a positive intege...
research
∙
06/29/2020
Pattern Masking for Dictionary Matching
In the Pattern Masking for Dictionary Matching (PMDM) problem, we are gi...
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/26/2019
String Sanitization: A Combinatorial Approach
String data are often disseminated to support applications such as locat...
research
∙
05/07/2019
Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
An elastic-degenerate (ED) string is a sequence of n sets of strings of ...
research
∙
02/13/2019
Constructing Antidictionaries in Output-Sensitive Space
A word x that is absent from a word y is called minimal if all its prope...
research
∙
10/04/2018
Longest Property-Preserved Common Factor
In this paper we introduce a new family of string processing problems. W...
research
∙
07/31/2018
Efficient Computation of Sequence Mappability
Sequence mappability is an important task in genome re-sequencing. In th...
research
∙
06/07/2018
Alignment-free sequence comparison using absent words
Sequence comparison is a prerequisite to virtually all comparative genom...
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/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
