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
∙
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 ...
research
∙
07/04/2023
Sliding suffix trees simplified
Sliding suffix trees (Fiala Greene, 1989) for an input text T over a...
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
∙
01/11/2023
Linear Time Online Algorithms for Constructing Linear-size Suffix Trie
The suffix trees are fundamental data structures for various kinds of st...
research
∙
11/08/2022
Computing palindromes on a trie in linear time
A trie 𝒯 is a rooted tree such that each edge is labeled by a single cha...
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
∙
07/09/2022
Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
Let two static sequences of strings P and S, representing prefix and suf...
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
∙
02/17/2022
RePair Grammars are the Smallest Grammars for Fibonacci Words
Grammar-based compression is a loss-less data compression scheme that re...
research
∙
02/09/2022
Cartesian Tree Subsequence Matching
Park et al. [TCS 2020] observed that the similarity between two (numeric...
research
∙
07/19/2021
Sensitivity of string compressors and repetitiveness measures
The sensitivity of a string compression algorithm C asks how much the ou...
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
∙
08/19/2020
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
The Burrows-Wheeler-Transform (BWT), a reversible string transformation,...
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/30/2020
Longest Square Subsequence Problem Revisited
The longest square subsequence (LSS) problem consists of computing a lon...
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/19/2020
A reduction of the dynamic time warping distance to the longest increasing subsequence length
The similarity between a pair of time series, i.e., sequences of indexed...
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
∙
05/02/2020
Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings
We deal with the problem of maintaining the suffix tree indexing structu...
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
∙
08/18/2019
The smallest grammar problem revisited
In a seminal paper of Charikar et al. on the smallest grammar problem, t...
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
∙
04/09/2019
Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries
The suffix tree, DAWG, and CDAWG are fundamental indexing structures of ...
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
∙
01/29/2019
Online Algorithms for Constructing Linear-size Suffix Trie
The suffix trees are fundamental data structures for various kinds of st...
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
O(n n)-time text compression by LZ-style longest first substitution
Mauer et al. [A Lempel-Ziv-style Compression Method for Repetitive Texts...
research
∙
06/01/2018