research
∙
08/04/2023
Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph
In this paper, we present the first study of the computational complexit...
share
research
∙
07/15/2023
Computing SEQ-IC-LCS of Labeled Graphs
We consider labeled directed graphs where each vertex is labeled with a ...
research
∙
07/05/2023
Linear-time computation of generalized minimal absent words for multiple strings
A string w is called a minimal absent word (MAW) for a string S if w doe...
research
∙
03/03/2023
On Sensitivity of Compact Directed Acyclic Word Graphs
Compact directed acyclic word graphs (CDAWGs) [Blumer et al. 1987] are a...
research
∙
02/06/2023
Optimal LZ-End Parsing is Hard
LZ-End is a variant of the well-known Lempel-Ziv parsing family such tha...
research
∙
10/14/2022
Space-Efficient STR-IC-LCS Computation
One of the most fundamental method for comparing two given strings A and...
research
∙
10/05/2022
Computing maximal generalized palindromes
Palindromes are popular and important objects in textual data processing...
research
∙
02/28/2022
Minimal Absent Words on Run-Length Encoded Strings
A string w is called a minimal absent word (MAW) for another string T if...
research
∙
06/03/2021
Position Heaps for Cartesian-tree Matching on Strings and Tries
The Cartesian-tree pattern matching is a recently introduced scheme of p...
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/24/2020
Lyndon Words, the Three Squares Lemma, and Primitive Squares
We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter ...
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
∙
11/12/2018
MR-RePair: Grammar Compression based on Maximal Repeats
We analyze the grammar generation algorithm of the RePair compression al...
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