research
∙
07/04/2023
Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
The directed acyclic word graph (DAWG) of a string y of length n is the ...
share
research
∙
10/05/2022
Computing maximal generalized palindromes
Palindromes are popular and important objects in textual data processing...
research
∙
06/02/2021
Counting Lyndon Subsequences
Counting substrings/subsequences that preserve some property (e.g., pali...
research
∙
06/02/2021
On the approximation ratio of LZ-End to LZ77
A family of Lempel-Ziv factorizations is a well-studied string structure...
research
∙
05/28/2021
Grammar Index By Induced Suffix Sorting
Pattern matching is the most central task for text indices. Most recent ...
research
∙
05/18/2021
Combinatorics of minimal absent words for a sliding window
A string w is called a minimal absent word (MAW) for another string T if...
research
∙
03/05/2021
Compressed Communication Complexity of Hamming Distance
We consider the communication complexity of the Hamming distance of two ...
research
∙
12/18/2020
The Parameterized Suffix Tray
Let Σ and Π be disjoint alphabets, respectively called the static alphab...
research
∙
06/03/2020
Computing Palindromic Trees for a Sliding Window and Its Applications
The palindromic tree (a.k.a. eertree) for a string S of length n is a tr...
research
∙
05/19/2020
On repetitiveness measures of Thue-Morse words
We show that the size γ(t_n) of the smallest string attractor of the nth...
research
∙
05/17/2020
Towards Efficient Interactive Computation of Dynamic Time Warping Distance
The dynamic time warping (DTW) is a widely-used method that allows us to...
research
∙
04/11/2020
Grammar-compressed Self-index with Lyndon Words
We introduce a new class of straight-line programs (SLPs), named the Lyn...
research
∙
02/17/2020
Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences
The equidistant subsequence pattern matching problem is considered. Give...
research
∙
02/17/2020
DAWGs for parameterized matching: online construction and related indexing structures
Two strings x and y over Σ∪Π of equal length are said to parameterized m...
research
∙
01/16/2020
Faster STR-EC-LCS Computation
The longest common subsequence (LCS) problem is a central problem in str...
research
∙
09/06/2019
Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
A substring u of a string T is called a minimal unique substring (MUS) o...
research
∙
06/13/2019
On Longest Common Property Preserved Substring Queries
We revisit the problem of longest common property preserving substring q...
research
∙
06/03/2019
Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets
We present the first worst-case linear time algorithm that directly comp...
research
∙
05/30/2019
Compact Data Structures for Shortest Unique Substring Queries
Given a string T of length n, a substring u = T[i.. j] of T is called a ...
research
∙
04/16/2019
Dynamic Packed Compact Tries Revisited
Given a dynamic set K of k strings of total length n whose characters ar...
research
∙
03/14/2019
Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings
For a string S, a palindromic substring S[i..j] is said to be a shortest...
research
∙
03/14/2019
The Parameterized Position Heap of a Trie
Let Σ and Π be disjoint alphabets of respective size σ and π. Two string...
research
∙
01/30/2019
Faster queries for longest substring palindrome after block edit
Palindromes are important objects in strings which have been extensively...
research
∙
01/30/2019
Computing runs on a trie
A maximal repeat, or run, in a string, is a periodically maximal substri...
research
∙
08/03/2018
Right-to-left online construction of parameterized position heaps
Two strings of equal length are said to parameterized match if there is ...
research
∙
06/13/2018