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...
share
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
∙
05/10/2023
Acceleration of FM-index Queries Through Prefix-free Parsing
FM-indexes are a crucial data structure in DNA alignment, for example, b...
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
∙
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
∙
07/06/2022
Computing NP-hard Repetitiveness Measures via MAX-SAT
Repetitiveness measures reveal profound characteristics of datasets, and...
research
∙
02/15/2022
Longest (Sub-)Periodic Subsequence
We present an algorithm computing the longest periodic subsequence of a ...
research
∙
01/18/2022
Computing Longest (Common) Lyndon Subsequences
Given a string T with length n whose characters are drawn from an ordere...
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
∙
04/19/2021
A Separation of γ and b via Thue–Morse Words
We prove that for n≥ 2, the size b(t_n) of the smallest bidirectional sc...
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/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/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
∙
11/16/2019
Constructing the Bijective BWT
The Burrows-Wheeler transform (BWT) is a permutation whose applications ...
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
∙
05/07/2019
Order-Preserving Pattern Matching Indeterminate Strings
Given an indeterminate string pattern p and an indeterminate string text...
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
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
Block Palindromes: A New Generalization of Palindromes
We propose a new generalization of palindromes and gapped palindromes ca...
research
∙
02/16/2018